|
|
MSU SE and Ural SU contest. Petrozavodsk training camp. Summer 2005B. Тараканы в зданииОграничение времени: 1.5 секунды Ограничение памяти: 64 МБ
Петя живёт в многоэтажном здании, причем квартиры в его подъезде находятся по одной на этаже. Петя много лет наблюдал за местной флорой и фауной. Особенно он заинтересовался динамикой популяции тараканов. Проводя замеры каждый месяц, он отметил следующие особенности:
-
Количество тараканов в каждой квартире измеряется
целым числом в диапазоне от 0 до N (N — целое неотрицательное число, не большее 30).
-
Количество тараканов в некоторой квартире в текущем месяце является функцией от трёх чисел: количества тараканов в предыдущем месяце в данной квартире и в квартирах над и под данной.
Петю заинтересовал вопрос о том, как может изменяться количество насекомых в популяции, развивающейся по данным правилам. Чтобы не рассматривать начало и конец здания,
где законы изменения численности насекомых могут быть более сложными, он перешёл к случаю бесконечного и вверх, и вниз небоскрёба. Будем считать, что количество
тараканов может убывать, если можно так расположить этих насекомых по квартирам (не более, чем по N в каждую), использовав при этом конечное число насекомых
(во всех квартирах, кроме конечного числа, тараканов нет), что в следующий месяц число тараканов в здании станет меньше. Аналогично, количество тараканов может возрастать, если можно так расположить этих насекомых по квартирам, использовав при этом конечное число насекомых, что в следующий месяц число тараканов в здании увеличится (возможно, станет бесконечным). Исходные данныеВ первой строке записано максимальное число тараканов N в квартире. Далее следует таблица значений функции, определяющей зависимость количества тараканов в текущем месяце в данной квартире от их количества в предыдущем месяце. Таблица разбита на N+1 блок, каждый из которых состоит из N+1 строки, содержащей N+1 число в пределах от 0 до N. В строке с номером i блока с номером j число с номером k содержит количество тараканов в квартире в текущем
месяце, если в предыдущием месяце в ней было j тараканов, в квартире под ней было i тараканов, а в квартире над ней было k тараканов. Нумерация блоков, строк в них и чисел в строках начинается с нуля. Вася вынес из своих наблюдений, что если в предыдущем месяце в данной квартире не было тараканов, а также не было тараканов в квартирах над ней и под ней, то и в следующем месяце в данной квартире тараканов не будет. РезультатНеобходимо вывести:
- =, если количество тараканов не может ни убывать, ни возрастать.
-
<, если количество тараканов может убывать, но не может возрастать.
- >, если количество тараканов может возрастать, но не может убывать.
- <>, если количество тараканов может и убывать, и возрастать.
Примерыисходные данные | результат |
---|
1
0 1
0 1
0 0
1 1
| =
| 2
0 0 0
0 0 0
0 0 0
1 1 1
1 1 1
1 1 1
2 2 2
2 2 2
2 2 0
| <
|
Автор задачи: Андрей Румянцев Источник задачи: Petrozavodsk summer training camp, August 2005.
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1381. Тараканы в здании |
|
|