ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам | Поиск |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 102944
Темы:    [ Динамическое программирование в игровых задачах ]
[ Построение перечислителя ]
Сложность: 4
Классы:
Название задачи: Отравленный пирог .
В корзину
Прислать комментарий

Условие

Для игры «Отравленный пирог» используется прямоугольный пирог, разделенный на M «строк» горизонтальными разрезами и на N «столбцов» – вертикальными. Таким образом, пирог должен быть разбит на M × N клеток, правая нижняя из которых «отравлена». Играют двое игроков, ходы делаются по очереди. Каждый ход заключается в том, что игрок выбирает одну из еще не съеденных клеток пирога и съедает все клетки, расположенные левее и выше выбранной (в том числе и выбранную). Проигрывает тот, кто съедает отравленную клетку.

Требуется написать программу, которая по заданной игровой позиции определяет все возможные выигрышные ходы для начинающего в этой позиции. 

Входные данные

Данные во входном файле расположены в следующем порядке: M, N (1 ≤ M, N ≤ 9), X1, ..., XM. Здесь Xi – число оставшихся клеток в i-м снизу горизонтальном ряду. Все числа во входном файле разделяются пробелами и/или символами перевода строки.

Выходные данные

В первую строку выходного файла необходимо вывести количество различных выигрышных ходов К, а в последующие K строк – сами выигрышные ходы.

Каждый ход задается парой чисел (i, j), где i – номер (снизу) горизонтального ряда, а j – номер (справа) вертикального ряда, которому принадлежит выбранная клетка (1 ≤ i ≤ M, 1 ≤ j ≤ N).

Пример входного файла

3 5
5 4 3

Пример выходного файла

1
3 1

Решение

Скачать архив тестов и решений

Пронумеруем все возможные позиции в этой игре (например, в порядке возрастания числа оставшихся клеток пирога). Для каждой позиции методом динамического программирования вычисляем, является ли она выигрышной или проигрышной для начинающего в ней игрока. Сначала помечаем позицию, в которой все клетки съедены, как выигрышную. Для очередной позиции это определяется следующим образом. Если существует ход из этой позиции в проигрышную (а оттуда будет ходить противник), то это выигрышный ход, и, значит, рассматриваемая позиция является выигрышной. Если же все ходы из данной позиции приводят в выигрышные позиции, то это означает, что как бы ни сходил начинающий, у его противника будет существовать выигрышный ход, и, следовательно, эта позиция для начинающего проигрышная.

Основная проблема в этой задаче – нужно так пронумеровать состояния игры, чтобы по состоянию можно было эффективно вычислить его номер, а по номеру – легко восстановить состояние.

Источники и прецеденты использования

книга
предмет информатика
Автор Беров В., Лапунов А., Матюхин В., Пономарев А.
Название Особенности национальных задач по информатике
Издательство Триада-С
Год издания 2000
глава
Номер 5
Название Комбинаторные алгоритмы
Задача
Номер 2

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .