eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Цветная матрица

Цветная матрица

Лимит времени 1 секунда
Лимит использования памяти 256 MiB

Дано поле n \times m, то есть с n строками и m столбиками.

Казак Ус хочет раскрасить клетки, используя минимальное количество цветов. Однако он не хочет, чтобы существовали две клетки одинакового цвета, манхэттенская расстояние между которыми равно k.

Напомним, что манхэттенское расстояние между двумя клетками (x_1, y_1) и (x_2, y_2) равно |x_1-x_2|+|y_1-y_2|.

Найдите минимальное количество цветов, которые для этого необходимы, а также выведите раскрашенное поле.

Входные данные

Первая строка содержит три целых числа n, m, k (1 \leq n, m, k \leq 100, k < \min(n, m)) — количество строк, столбиков, фиксированное манхэттенское расстояние.

Выходные данные

В первой строке выведите наименьшее необходимое количество цветов t.

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

Если есть несколько возможных таблиц, то выведите любую из них.

Пример

Входные данные #1
2 2 1
Выходные данные #1
2
0 1 
1 0 
Входные данные #2
4 4 2
Выходные данные #2
4
0 2 3 1 
0 1 3 2 
3 1 0 2 
3 2 0 1 

Примечание

В первом примере позиции (1,1) и (2,2) имеют цвет 0, а позиции (1,2) и (2,1) цвет 1. Между позициями (1,1) и (1,2) манхэттенская расстояние |1-1|+|1-2|=1. Поскольку k=1, то эти две позиции должны иметь разные цвета. А вот между позициями (1,2) и (2,1) расстояние |1-2|+|2-1|=2. Поэтому они могут иметь одинаковый цвет.

Оценивание

  1. (17 баллов): k=1;

  2. (18 баллов): k=2;

  3. (14 баллов): k=3;

  4. (13 баллов): k=4;

  5. (24 баллов): k — нечетное;

  6. (14 баллов): без дополнительных ограничений.

Автор Денис Слободянюк
Источник 2021 Всеукраинская олимпиада по информатике, Этап IV, Раунд II