eolymp
bolt
Try our new interface for solving problems
Məsələlər

Тараканы в здании

Тараканы в здании

Zaman məhdudiyyəti 1.5 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

Петя живёт в многоэтажном здании, причем квартиры в его подъезде находятся по одной на этаже. Петя много лет наблюдал за местной флорой и фауной. Особенно он заинтересовался динамикой популяции тараканов. Проводя замеры каждый месяц, он отметил следующие особенности:

  • Количество тараканов в каждой квартире измеряется целым числом в диапазоне от 0 до N (N — целое неотрицательное число, не большее 30).

  • Количество тараканов в некоторой квартире в текущем месяце является функцией от трёх чисел: количества тараканов в предыдущем месяце в данной квартире и в квартирах над и под данной.

Петю заинтересовал вопрос о том, как может изменяться количество насекомых в популяции, развивающейся по данным правилам. Чтобы не рассматривать начало и конец здания, где законы изменения численности насекомых могут быть более сложными, он перешёл к случаю бесконечного и вверх, и вниз небоскрёба. Будем считать, что количество тараканов может убывать, если можно так расположить этих насекомых по квартирам (не более, чем по N в каждую), использовав при этом конечное число насекомых (во всех квартирах, кроме конечного числа, тараканов нет), что в следующий месяц число тараканов в здании станет меньше. Аналогично, количество тараканов может возрастать, если можно так расположить этих насекомых по квартирам, использовав при этом конечное число насекомых, что в следующий месяц число тараканов в здании увеличится (возможно, станет бесконечным).

Giriş verilənləri

В первой строке записано максимальное число тараканов N в квартире. Далее следует таблица значений функции, определяющей зависимость количества тараканов в текущем месяце в данной квартире от их количества в предыдущем месяце. Таблица разбита на N+1 блок, каждый из которых состоит из N+1 строки, содержащей N+1 число в пределах от 0 до N. В строке с номером i блока с номером j число с номером k содержит количество тараканов в квартире в текущем месяце, если в предыдущием месяце в ней было j тараканов, в квартире под ней было i тараканов, а в квартире над ней было k тараканов. Нумерация блоков, строк в них и чисел в строках начинается с нуля. Вася вынес из своих наблюдений, что если в предыдущем месяце в данной квартире не было тараканов, а также не было тараканов в квартирах над ней и под ней, то и в следующем месяце в данной квартире тараканов не будет.

Çıxış verilənləri

Необходимо вывести:

  • =, если количество тараканов не может ни убывать, ни возрастать.

  • <, если количество тараканов может убывать, но не может возрастать.

  • >, если количество тараканов может возрастать, но не может убывать.

  • <>, если количество тараканов может и убывать, и возрастать.

Nümunə

Giriş verilənləri #1
1
0 1
0 1

0 0
1 1
Çıxış verilənləri #1
=
Müəllif Андрей Румянцев
Mənbə Petrozavodsk summer training camp, August 2005