Олимпиада по информатике 2025-2026 муниципальный этап Хомячья раскраска

Олимпиада по информатике 2025-2026 муниципальный этап Хомячья раскраска

olimp-inf-tatmunits-2025-A

Задача «Хомячья раскраска» — решение на Python

Идея решения

Цвет клетки задаётся по формуле:
color(i, j) = ((i + j - 2) mod k) + 1, то есть цвет зависит только от суммы индексов.
Рассмотрим остатки:
r = (i - 1) mod k, s = (j - 1) mod k.
Тогда (i + j - 2) mod k = (r + s) mod k.
Посчитаем, сколько строк даёт каждый остаток r,
и сколько столбцов даёт каждый остаток s.
Каждая пара остатков (r, s) даёт
rows[r] * cols[s] клеток цвета
t = (r + s) mod k.
Так как k ≤ 5, можно просто перебрать все пары остатков
(не более 25 вариантов).

Код на Python

import sys

data = list(map(int, sys.stdin.read().split()))
n, m, k = data[0], data[1], data[2]

# Count of residues for rows (0..n-1) and columns (0..m-1)
cntN = [n // k] * k
for a in range(n % k):
    cntN[a] += 1

cntM = [m // k] * k
for a in range(m % k):
    cntM[a] += 1

ans = [0] * k  # ans[r] for color r+1

for r in range(k):
    total = 0
    for a in range(k):
        b = (r - a) % k
        total += cntN[a] * cntM[b]
    ans[r] = total

# Output k lines: i-th line is count for color i
out_lines = "\n".join(str(x) for x in ans)
print(out_lines)

import sys

data = list(map(int, sys.stdin.read().split()))

n, m, k = data[0], data[1], data[2]

# Count of residues for rows (0..n-1) and columns (0..m-1)

cntN = [n // k] * k

for a in range(n % k):

cntN[a] += 1

cntM = [m // k] * k

for a in range(m % k):

cntM[a] += 1

ans = [0] * k # ans[r] for color r+1

for r in range(k):

total = 0

for a in range(k):

b = (r - a) % k

total += cntN[a] * cntM[b]

ans[r] = total

# Output k lines: i-th line is count for color i

out_lines = "\n".join(str(x) for x in ans)

print(out_lines)