Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
994. Игра
ИгрыОлимпиадные задачи на русском языке
| 03/07/2008 | Лето 2008 дорешивание ( 7I) |
| 16/07/2008 | Лето 2008 - 7 (I) |
| 19/03/2014 | Занятие 17 (C) |
Ограничения: время – 1s/2s, память – 8MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Одно время в среде охочих до игр комсомольцев была в ходу придуманная кем-то случайно игра. Проходит она на поле размером `N\ times\ N` (`4\ ≤\ N\ ≤\ 100`), в каждой клетке которого записано число от 1 до `N`.
Правила:
- Игроки делают ходы по очереди.
- Первым ходом первый игрок ставит фишку на одну из клеток самого левого столбца поля.
- На втором и последующих ходах игроки могут двигать фишку вправо, вверх или вниз на количество позиций от 1 до числа, записанного в той клетке, на которой стоит фишка перед началом хода.
- Фишка во время хода НЕ может проходить через уже пройденные клетки, то есть не может пересечь свою предыдущую траекторию. Также фишка не должна выходить за пределы игрового поля.
- Игра заканчивается, как только фишка оказывается в крайнем правом столбце, при этом игрок, сделавший последний ход, выигрывает.
Спрашивается, какой игрок победит, если известна конфигурация игрового поля, и оба игрока играют оптимально.
Ввод
На первой строке входного файла – число `N`. Описание игрового поля содержится в последующих `N` строках, в каждой из которых находятся `N` чисел из отрезка `[1,N]`, разделенных пробелами.
Вывод
В выходном файле должно содержаться единственное число:
1 – если победит первый игрок
2 – если победит второй игрок
Пример ввода 1
4 1 2 2 2 1 1 1 1 1 2 1 1 1 1 2 1
Пример вывода 1
1
Пример ввода 2
4 2 2 1 2 1 2 1 2 2 2 2 1 2 1 2 2
Пример вывода 2
2
