ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

MSU SE and Ural SU contest. Petrozavodsk training camp. Summer 2005

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

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

Ограничение времени: 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. Тараканы в здании