Главная › Информатика › №20 · Теория игр (20)

ЕГЭ информатика, задание 20: №20 · Теория игр (20)

Два игрока, Петя и Ваня, играют в игру. Перед ними лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один камень, или добавить четыре камня, или увеличить количество камней в два раза. Игра завершается, когда количество камней в куче становится не менее 57. Победителем считается игрок, сделавший последний ход. В начальный момент в куче было S камней, 1 ≤ S ≤ 56. Найди два наименьших значения S, при которых у Пети есть выигрышная стратегия, причём Петя не может выиграть за один ход и Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня. Запиши их в порядке возрастания через пробел.

Показать ответ и разбор
Ответ: 14 24

Ищем S, из которых Петя одним ходом ставит Ваню в проигрышную позицию (любой ход Вани даёт Пете выигрыш сразу). Два наименьших: 14 и 24.

Лайфхак. рекурсивная функция игры с параметрами (s, ход) решает 19–21 сразу.
Потренируйся в боте. Такие задания с разбором, статистика по темам и работа над ошибками: бесплатно в Telegram.
Решить это задание в боте @infkostbot

Ещё задания по теме