1968 - Bloc

Cerinţa

Cifrele de la 1 la K se scriu într-un şir, iar secvenţa obţinută se repetă la nesfârşit. De exemplu, pentru K=9 se obţine şirul: 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 …. Asupra unui asemenea şir se aplică succesiv operaţia de rostogolire de lungime P, ce presupune ca blocul format cu cifrele de pe primele P poziţii să se rotească cu 1800 şi să se scrie deasupra următoarei secvenţe de lungime P. În cazul exemplului anterior, pentru P=3, vom obţine după 4 operaţii de rostogolire de lungime 3: Pas 1: 3 2 1

    4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9…

Pas 2: 6 5 4

    1 2 3
    7 8 9 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9…

Pas 3: 9 8 7

    3 2 1
    4 5 6
    1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9…

Pas 4: 3 2 1

    6 5 4
    1 2 3
    7 8 9
    4 5 6 7 8 9 1 2 3 4 5 6 7 8 9…

Astfel pe primele P poziţii se formează un bloc având la bază P cifre şi înălţimea N+1, unde N este numărul de rostogoliri de lungime P. Pentru K, P şi N date se cer următoarele: a) Suma elementelor blocului după N rostogoliri de lungime P. b) Suma maximă a elementelor de pe o coloană a blocului după N rostogoliri de lungime P. c) Dacă liniile blocului le privim ca pe nişte numere cu P cifre, să se afle cel mai mic dintre aceste numere ale blocului obţinut după N rostogoliri de lungime P.

Date de intrare

Fişierul de intrare bloc.in conţine pe prima linie numerele K, P şi N ce reprezintă cifra maximă din şirul iniţial, lungimea secvenţei care se rostogoleşte, respectiv numărul de rostogoliri.

Date de ieșire

Fişierul de ieşire bloc.out va conţine pe prima linie suma elementelor blocului după N rostogoliri, pe a doua linie suma maximă a elementelor unei coloane a blocului după N rostogoliri, iar pe a treia linie numărul minim format din cifrele unei linii a blocului după N rostogoliri.

Restricţii şi precizări

• 1 ≤ K ≤ 9
• 1 ≤ P ≤ 100
• 1 ≤ N ≤ 1.000.000
• Prima cerinţă se notează cu 40p, a doua cu 40p, iar a treia cu 20p

Exemplul 1

bloc.in

 9 3 4

bloc.out

 66
 23
 123

Explicație

Datele corespund exemplului de mai sus. La pasul 4 suma elementelor blocului este 66, coloana a treia a blocului are suma 1+4+3+9+6=23 care este maximă, iar cifrele de pe linia a treia a blocului formează numărul minim 123.

Rezolvare

def rotate_sequence(sequence, P):
    return sequence[P-1::-1] + sequence[P:]

def rotate_block(block, P):
    return [rotate_sequence(row, P) for row in block]

def sum_block(block):
    return sum(sum(row) for row in block)

def max_column_sum(block):
    max_sum = 0
    for j in range(len(block[0])):
        column_sum = sum(block[i][j] for i in range(len(block)))
        max_sum = max(max_sum, column_sum)
    return max_sum

def min_line_number(block):
    min_number = int(''.join(map(str, block[0])))
    for row in block[1:]:
        number = int(''.join(map(str, row)))
        min_number = min(min_number, number)
    return min_number

def main():
    with open("bloc.in", "r") as fin:
        K, P, N = map(int, fin.readline().split())

    sequence = [i % K + 1 for i in range(K * 2)]
    block = [sequence[i:i+P] for i in range(0, P*(N+1), P)]

    for _ in range(N):
        block = rotate_block(block, P)

    sum_elements = sum_block(block)
    max_column = max_column_sum(block)
    min_line = min_line_number(block)

    with open("bloc.out", "w") as fout:
        fout.write(f"{sum_elements}\n")
        fout.write(f"{max_column}\n")
        fout.write(f"{min_line}\n")

if __name__ == "__main__":
    main()