НачалоПодразделы
Другие разделы
| 986. День программиста |
| 987. Сад |
| 988. Квадраты |
| 989. Баллы для тестов |
| 990. Пароль |
| 991. Ил-2 |
| 992. Простая сумма |
| 993. Веселые шахматы |
| 995. Вектор |
Дата и время
04/12/2024 14:00:38
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
