#40

Перекраска клеток

Темы: [Система непересекающихся множеств] [Двумерные массивы] [Список]

Источники: [ Командные олимпиады, Московская командная олимпиада, 9-11 классы, 2006, Задача E ]

+

+

(4,3)

+

+

Дано клетчатое поле N x M, все клетки поля изначально белые. Автомат умеет:

закрасить клетку (i,j) в черный цвет.
для клетки (i,j) узнать её ближайших белых соседей по вертикали и горизонтали.

Дана последовательность команд для автомата. Требуется выполнить эти команды в указанной последовательности, и для каждой команды запроса ближайших белых соседей указать результат ее выполнения.

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

Сначала вводятся размеры поля N и M (1 ≤ N ≤ 20, 1 ≤ M ≤ 50000), затем количество команд K (1 ≤ K ≤ 10⁵), а затем сами команды. Команды записаны по одной в строке в следующем формате:

Colori j — окраска клетки (i,j) в черный цвет;
Neighbors i j — нахождение белых соседей для БЕЛОЙ клетки (i,j).

1 ≤ i ≤ N, 1 ≤ j ≤ M.

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

На каждый запрос Neighbors требуется вывести сначала количество ближайших белых соседей (или 0, если ни с одной из сторон белых клеток не осталось), а затем их координаты (соседей можно перечислять в произвольном порядке). Если запросов Neighbors нет, ничего выводить не надо. Пример ниже некорректен, первое число "3" должно отсутствовать.

Оценка задачи

1 балл получат решения, верно работающие при N ≤ 20, M ≤ 500, K ≤ 1000.

Примеры

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

5 5 6
Color 4 2
Neighbors 4 3
Color 2 3
Color 3 3
Neighbors 4 3
Neighbors 5 1

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

#405

Цифровое табло

Темы: [Задачи на моделирование] [Двумерные массивы]

Источники: [ Командные олимпиады, ВКОШП, 2006, Задача C ]

Изображение задается отрезками, параллельными осям координат или под углом 45 градусов к ним. Необходимо вывести таблицу, где все отрезки имеют ширину k клеток.

В комнате у Аркадия Семеновича Тапкина стоят электронные часы. Цифры на этих часах показываются в специальной псевдографике. А именно, каждое поле, на котором изображается цифра, состоит из w ячеек в ширину и h ячеек в высоту (при этом ячейки на поле имеют форму квадратов).

Но недавно у Аркадия Семеновича появилась проблема. Последнее время он стал плохо видеть. В связи с этим он хочет увеличить изображение этих цифр. Он уже приладил старый 19'' монитор к часам, и теперь дело осталось за малым. Осталось написать программу, которая будет рисовать цифры на дисплее. Аркадий Семенович хочет увеличить изображение в k раз и сделать толщину линий равной d. Помогите ему в этом.

Опишем более формально понятие «увеличить в k раз». Занумеруем ячейки поля w×h сверху вниз и слева направо. Таким образом, верхняя левая ячейка имеет координаты (0, 0), правая нижняя – (w - 1, h - 1), правая верхняя – (w - 1, 0), левая нижняя – (0, h - 1). Кроме этого, введем декартову прямоугольную систему координат так, что начало координат находится в центре верхней левой ячейки, ось Ox направлена вправо, ось Oy – вниз, длину единичного отрезка примем равной длине стороны ячейки. Таким образом, координаты центра ячейки совпадают с ее координатами во введенной нумерации.

Каждая десятичная цифра задается набором составляющих ее изображение отрезков. Для простоты каждый из отрезков либо параллелен одной из координатных осей, либо идет под углом в 45 градусов к ней.

Увеличенная в k раз цифра рисуется на поле размером (w - 1)^.(k - 1) + w ячеек по горизонтали на (h - 1)^.(k - 1) + h ячеек по вертикали.

При увеличении некоторой цифры в k раз производятся следующие операции. Координаты точек, являющихся концами отрезков, составляющих цифру, умножаются на k. После этого закрашиваются те ячейки, через центры которых проходят эти отрезки. Эти ячейки будем называть основными.

После этого, для того, чтобы получить толщину линий равную d, дополнительно закрашиваются те ячейки, центры которых располагаются на расстоянии, не превышающем (d - 1) от центров основных ячеек. Расстоянием между точками A(x_A, y_A) и B(x_B, y_B) будем называть число $rho$ (A, B) = | x_A - x_B| + | y_A - y_B|.

По описанию цифры и параметрам k и d выведите изображение цифры, увеличенное в k раз, с толщиной линий d.

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

В первой строке вводятся числа k и d ( 1 $le$ k $le$ 100, 1 $le$ d $le$ 500). Вторая строка содержит целые числа w и h ( 1 $le$ w, h $le$ 10).

В третьей строке задается целое число n ( 1 $le$ n $le$ 100) – количество отрезков в описании цифры. Далее следуют n строк, каждая из которых описывает один отрезок. Описание отрезка состоит из четырех целых чисел: x₁, y₁, x₂, y₂ ( 0 $le$ x₁, x₂ < w, 0 $le$ y₁, y₂ < h) – координат концов отрезка.

Каждый из отрезков либо параллелен одной из координатных осей, либо идет под углом в 45 градусов к ней. Все отрезки имеют ненулевую длину.

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

Программа должна вывести ровно (h - 1)^.(k - 1) + h строк по (w - 1)^.(k - 1) + w символов в каждой, j-ый символ i-ой строки должен быть равен символу «*» (звездочка), если ячейка с центром в точке (j, i) закрашена, и символу «.» (точка) – иначе.

Примеры

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

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

****
...*
...*
...*
...*
...*

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

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

*******
......*
......*
......*
......*
.....*.
....*..
...*...
..*....
.*.....
*******

#427

Приключения на шахматной доске

Темы: [Условный оператор (if)] [Двумерные массивы] [Быстрая сортировка]

Источники: [ Командные олимпиады, ВКОШП, 2004, Задача E ]

В двумерном массиве записаны числа. Числа формируются следующим образом: ставится шахматный ферзь и на клетку записывается число. Ферзем делается любой ход и на клетку, на которую он попал, ставится число, большее предыдущего. Необходимо проверить корректность и вывести последовательность ходов.

Ваня очень любит шахматы. Причем он не только любит просто играть в шахматы, но часто придумывает разные головоломки и просто забавные задачки с использованием шахматных фигур. Также вместо стандартной шахматной доски 8×8 Ваня часто использует в своих задачах доски другого размера.

Недавно он придумал новую головоломку и рассказал ее своим друзьям. Суть головоломки заключается в следующем. На одно из полей доски размером m×n записывается некоторое положительное целое число и затем на него ставится ферзь.

После этого Ваня делает k ходов ферзем, каждый раз перемещая его по шахматным правилам на одно из полей, на котором он еще не был. При этом каждый раз, перед тем как поставить ферзя на некоторое поле, он записывает на это поле целое число, причем это число всегда больше всех чисел, уже записанных на доске.

Задача друзей Вани – по числам, записанным на доске, восстановить маршрут ферзя или выяснить, что Ваня где-то ошибся. Поскольку Ваня часто выбирает достаточно большие m, n и k, друзья устали решать эту головоломку вручную и решили написать для ее решения программу. Помогите им

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

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

В первой строке вводятся числа m, n и k ( 1 $le$ m, n $le$ 300, 0 $le$ k < mn). Следующие m строк содержат по n целых чисел и описывают поля доски (пустому полю соответствует число 0, а полю, на котором записано число – это число). Все числа, записанные на доске, положительные, целые и не превышают 10⁹.

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

Если Ваня ошибся при построении головоломки, выведите сообщение «Wrong Board».

В противном случае выведите m строк по n чисел – для каждого поля выведите номер хода, перед которым ферзь побывал на этом поле, а для последнего поля, на котором он оказался – число k + 1. Для полей, на которые ферзь не попадал, выведите число 0.

Примеры

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

4 4 7
10 20 0 100
30 0 0 40
0 0 0 0
45 42 0 70

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

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

2 4 4
10 20 30 40
0 50 0 0

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

Wrong Board

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

2 2 2
1 2
4 3

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

Wrong Board

#505

Жизнь в квадрате

Темы: [Двумерные массивы]

Источники: [ Командные олимпиады, Московская командная олимпиада, 8 класс, 2007, Задача A ]

В некоторых клетках квадрата $N$ x $N$ живут микроорганизмы (не более одного в одной клетке). Каждую секунду происходит следующее:
– все микроорганизмы, у которых менее 2-х соседей, умирают от скуки (соседями называются микроорганизмы, живущие в клетках, имеющих общую сторону или вершину);
– все микроорганизмы, у которых более 3-х соседей, умирают от перенаселенности;
– на всех пустых клетках, у которых ровно в трех соседних клетках жили микроорганизмы, появляются новые микроорганизмы.
Все изменения происходят одновременно, то есть для каждой клетки сначала выясняется ее судьба, а затем происходят изменения сразу во всех клетках.
Требуется по данной конфигурации определить, во что она превратится через $T$ секунд.

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

В первой строке вводятся два натуральных числа – $N$ (1 ≤ $N$ ≤ 10) и $T$ (1 ≤ $T$ ≤ 100). Далее записано $N$ строчек по $N$ чисел, описывающих начальную конфигурацию (0 – пустая клетка, 1 – микроорганизм). Числа в строках разделены пробелами.

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

Требуется вывести $N$ строк по $N$ чисел – описание конфигурации через $T$ секунд (в том же формате, как и во входных данных).

Примеры

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

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

0 0 0 
1 0 1 
0 0 0

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

2 2
1 1
1 1

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

1 1 
1 1

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

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

#526

Мурка ест траву

Темы: [Двумерные массивы]

Источники: [ Командные олимпиады, Московская командная олимпиада, 8 класс, 2006, Задача B ]

Пастбище представляет собой прямоугольник, разбитый на $N$ x $N$ клеток. В каждой клетке растет трава, имеющая свою калорийность (во всех клетках калорийность травы разная). В левой нижней клетке стоит корова Мурка. Съев всю траву в своей клетке, она перемещается на одну клетку вправо или на одну клетку вверх, всегда выбирая ту из клеток, калорийность травы в которой больше (за пределами поля трава не растет). В конце концов корова приходит в правую верхнюю клетку. Требуется определить, сколько всего калорий получит корова (считая калории травы в первой и в последней клетках).

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

Сначала вводится число $N$ – размер поля (2 ≤ $N$ ≤ 10). В следующей строке вводятся через пробел числа, задающие количество калорий в клетках верхнего ряда, в следующей – количество калорий в клетках следующего ряда, …, в последней – количество калорий в клетках нижнего ряда. Все числа – различные, натуральные, не превосходящие 100.

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

Требуется вывести количество калорий, которое получит корова.

Примеры

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

2
37 82
23 52

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