|
+ |
||||
|
+ |
(4,3) |
+ |
||
|
+ |
Дано клетчатое поле N x M, все клетки поля изначально белые. Автомат умеет:
Дана последовательность команд для автомата. Требуется выполнить эти команды в указанной последовательности, и для каждой команды запроса ближайших белых соседей указать результат ее выполнения.
Сначала вводятся размеры поля N и M (1 ≤ N ≤ 20, 1 ≤ M ≤ 50000), затем количество команд K (1 ≤ K ≤ 105), а затем сами команды. Команды записаны по одной в строке в следующем формате:
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
3 4 4 1 4 4 3 3 5 3 4 4 1 4 4 1 3 5 3 2 5 2 4 1
В некоторых клетках квадрата \(N\) x \(N\) живут микроорганизмы (не более одного в одной клетке). Каждую секунду происходит следующее:
– все микроорганизмы, у которых менее 2-х соседей, умирают от скуки (соседями называются микроорганизмы, живущие в клетках, имеющих общую сторону или вершину);
– все микроорганизмы, у которых более 3-х соседей, умирают от перенаселенности;
– на всех пустых клетках, у которых ровно в трех соседних клетках жили микроорганизмы, появляются новые микроорганизмы.
Все изменения происходят одновременно, то есть для каждой клетки сначала выясняется ее судьба, а затем происходят изменения сразу во всех клетках.
Требуется по данной конфигурации определить, во что она превратится через \(T\) секунд.
В первой строке вводятся два натуральных числа – \(N\) (1 ≤ \(N\) ≤ 10) и \(T\) (1 ≤ \(T\) ≤ 100). Далее записано \(N\) строчек по \(N\) чисел, описывающих начальную конфигурацию (0 – пустая клетка, 1 – микроорганизм). Числа в строках разделены пробелами.
Требуется вывести \(N\) строк по \(N\) чисел – описание конфигурации через \(T\) секунд (в том же формате, как и во входных данных).
3 1 1 0 1 1 0 1 1 0 1
0 0 0 1 0 1 0 0 0
2 2 1 1 1 1
1 1 1 1
5 10 1 0 1 1 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 1 0
0 1 1 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Пастбище представляет собой прямоугольник, разбитый на \(N\) x \(N\) клеток. В каждой клетке растет трава, имеющая свою калорийность (во всех клетках калорийность травы разная). В левой нижней клетке стоит корова Мурка. Съев всю траву в своей клетке, она перемещается на одну клетку вправо или на одну клетку вверх, всегда выбирая ту из клеток, калорийность травы в которой больше (за пределами поля трава не растет). В конце концов корова приходит в правую верхнюю клетку. Требуется определить, сколько всего калорий получит корова (считая калории травы в первой и в последней клетках).
Сначала вводится число \(N\) – размер поля (2 ≤ \(N\) ≤ 10). В следующей строке вводятся через пробел числа, задающие количество калорий в клетках верхнего ряда, в следующей – количество калорий в клетках следующего ряда, …, в последней – количество калорий в клетках нижнего ряда. Все числа – различные, натуральные, не превосходящие 100.
Требуется вывести количество калорий, которое получит корова.
2 37 82 23 52
157
Сережа играет в "Морской бой". Поле для игры представляет собой квадрат 10 x 10 клеток. На поле отмечены клетки, в которые Сережа уже стрелял. Однако, пока он не попал ни в один корабль противника. Требуется определить максимальную длину корабля, который может поместиться в небитых клетках этого поля. Корабль представляет из себя прямоугольник ширины 1 и располагается горизонтально или вертикально. (Гарантируется, что на поле есть хотя бы одна небитая клетка.)
Вводятся 10 строк по 10 чисел в каждой, числа разделены пробелами. Число 1 означает, что в соответствующую клетку стреляли, число 0 – что в клетку не стреляли.
Требуется вывести одно число от 1 до 10 – максимальную возможную длину корабля.
0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0
10
Прямоугольную таблицу, состоящую из N строк и M столбцов, раскрашивают следующим образом. Каждый столбец таблицы и каждую строку красят либо в синий, либо в желтый цвет. В итоге клетки, оказавшиеся на пересечении синего столбца и синей строки оказываются синими, желтого столбца и желтой строки — желтыми, а клетки на пересечении синего столбца и желтой строки, или, наоборот, желтого столбца и синей строки — зелеными.
Раскраска всех клеток таблицы (или просто сама таблица) называется правильной, если она может быть получена описанным выше способом.
Вам дана прямоугольная таблица, которую нужно раскрасить таким образом. Про некоторые клетки известно, какого цвета они должны быть, а остальные клетки могут в итоге быть любого цвета. Определите, как нужно раскрасить остальные клетки таблицы, чтобы раскраска была правильной.
Вводятся числа N и M — количество строк и столбцов таблицы (1≤N≤30, 1≤M≤30). Далее записано N строк по M чисел в каждой, задающие цвета, в которые должны быть окрашены клетки:
0 — клетка может в итоге быть любого цвета
1 — клетка должна быть синей
2 — клетка должна быть желтой
3 — клетка должна быть зеленой
Выведите N строк по M чисел в каждой — раскраску таблицы, которая является правильной, и в которой нужные клетки имеют нужный цвет. Если вариантов несколько, выведите любой из них. Если покрасить таким образом таблицу невозможно, выведите одно число 0.
Примеры
| Входные данные | Выходные данные |
| 3 4 1 0 0 0 3 0 0 0 0 0 0 0 | 1 1 1 1 3 3 3 3 1 1 1 1 |
| 2 2 3 3 3 3 | 3 3 3 3 |
| 2 2 2 2 2 3 | 0 |