0262. Цветы

Input file name: flowers.in
Output file name: flowers.out
Time limit: 2 s
Memory limit: 64 megabytes

Перед главным входом Университета ректор приказал посадить клумбу из цветов (для облагораживания внешнего вида Университета). Почему-то клумбу поручили делать студентам математического факультета. Как-то так вышло, но сама клумба получилась квадратной. Более того, растения, которые были заказаны студентами, тоже оказались квадратными (если смотреть на них сверху). Тогда студенты гарантировали, что все растения можно в эту клумбу посадить каким-то образом. Но далее они уехали на чемпионат мира по программированию, а тут привезли цветы. Что же делать? Куда что сажать? Эту задачу и поручили Вам. Итак, клумба представляет из себя квадрат размера N * N дециметров, разбитый на N*N одинаковых квадратиков. Цветы представляют из себя квадраты со стороной K дециметров. Заметим, что деления на рулетке, которая есть у Вас, представляют собой целые дециметры, поэтому от границ цветка до границ клумбы должно быть целое число дм. Кроме того, известно, что для обеспечения нормального роста растений их нужно сажать таким образом, чтобы границы цветка были параллельны границам клумбы. Необходимо указать какой-то способ размещения цветов. Гарантируется, что хотя бы один такой способ есть.

Формат входного файла

В первой строке входного файла записаны числа N - размер клумбы (1 ≤ N ≤ 1000) и M - количество цветов (1 ≤ M ≤ 1000000). Далее M строк, в каждой по одному числу K - размер цветка (0 < K < 3). Все числа целые.

Формат выходного файла

Вывести матрицу N*N, в которой i-тое число в j-той строке определяет, какому цветку принадлежит клетка (j, i). Если это число равно 0, то клетка свободна. В противном случае в ней записан номер цветка, которому она принадлежит. Цветки нумеруются с 1, в порядке их следования во входном файле.

Пример:

flowers.inflowers.out
5 7 2 1 1 1 2 2 1 3 0 5 5 2 0 7 5 5 0 6 6 4 0 0 6 6 0 1 1 0 0 0 1 1


Source: Первенство первокурсника ПетрГУ. Осень 2006.

Discuss       Submit a solution



Printable version