Кольорова матриця#10444

Кольорова матриця

1 секунда

256 мегабайтів

Середня

Дано поле $n \times m$ n \times m, тобто з $n$ рядками та $m$ стовпчиками.

Козак Вус хоче розфарбувати клітини, використовуючи мінімальну кількість кольорів. Проте він не хоче, щоб існували дві клітини однакового кольору, манхеттенська відстань між якими дорівнює $k$ .

Нагадаємо, що манхеттенська відстань між двома клітинами $(x_{1}, y_{1})$ (x_1, y_1) та $(x_{2}, y_{2})$ (x_2, y_2) дорівнює $∣ x_{1} - x_{2} ∣ + ∣ y_{1} - y_{2} ∣$ |x_1-x_2|+|y_1-y_2|.

Знайдіть мінімальну кількість кольорів, які для цього потрібні, а також виведіть розфарбоване поле.

Вхідні дані

Перший рядок містить три цілі числа $n$ , $m$ , $k$ ( $1 \leq n, m, k \leq 100$ 1 \leq n, m, k \leq 100, $k < min (n, m)$ k < \min(n, m)) — кількість рядків, стовпчиків, фіксована манхеттенська відстань.

Вихідні дані

В першому рядку виведіть найменшу необхідну кількість кольорів $t$ .

В кожному з наступних $n$ рядків виведіть $m$ чисел — номери кольорів відповідних клітинок таблиці ( $0 \leq c_{i, j} \leq t - 1$ 0 \leq c_{i,j} \leq t-1).

Якщо є кілька можливих таблиць, то можна вивести будь-яку з них.

Приклади

Приклад 1

Приклад 2

Примітка

У першому прикладі позиції $(1, 1)$ та $(2, 2)$ мають колір $0$ , а позиції $(1, 2)$ та $(2, 1)$ колір $1$ . Між позиціями $(1, 1)$ та $(1, 2)$ манхеттенська відстань $∣1 - 1∣ + ∣1 - 2∣ = 1$ |1-1|+|1-2|=1. Оскільки $k = 1$ k=1, то ці дві позиції повинні мати різні кольори. А от між позиціями $(1, 2)$ та $(2, 1)$ відстань $∣1 - 2∣ + ∣2 - 1∣ = 2$ |1-2|+|2-1|=2. Тому вони можуть мати однаковий колір.

Оцінювання

( $17$ балів): $k = 1$ k=1;
( $18$ балів): $k = 2$ k=2;
( $14$ балів): $k = 3$ k=3;
( $13$ балів): $k = 4$ k=4;
( $24$ балів): $k$ — непарне;
( $14$ балів): без додаткових обмежень.