Задача к ЕГЭ по информатике на тему «Условие проигрыша» №1

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу три камня, четыре камня или увеличить количество камней в куче в два раза. Например, имея кучу из $10$ камней, за один ход можно получить кучу из $13$ , $14$ или $20$ камней. Чтобы делать ходы, у каждого игрока есть неограниченное количество камней. Игра завершается в тот момент, когда количество камней в куче становится не менее $52$ . Если при этом в куче оказалось не более $78$ камней, то победителем считается игрок, сделавший последний ход. В противном случае победителем становится его противник.

В начальный момент в куче было $S$ камней, $1 ≤ S ≤ 51.$

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

Найдите максимальное значение $S$ , при котором Ваня выигрывает своим первым ходом при любой игре Пети.

from functools import lru_cache


@lru_cache(None)
def game(heap):  # Функция игры

    # Если кол-во камней в куче стало более 78
    if heap > 78:
        # Возвращаем 1,
        # которая преобразуется в победу Вани первым ходом из-за "плохого" хода Пети
        return 1

    # Если кол-во камней в куче стало не менее 52
    if heap >= 52:
        return 0  # Прекращаем игру

    # Прописываем возможные ходы в партии
    moves = [game(heap + 3), game(heap + 4), game(heap * 2)]

    # Находим значения, через которые может победить Петя
    petya_win = [i for i in moves if i <= 0]

    if petya_win:  # Если такие значения нашлись и список не пуст
        return -max(petya_win) + 1
    else:  # Иначе побеждает Ваня максимальным ходом
        return -max(moves)


for S in range(1, 51 + 1):  # Перебор значений S
    if game(S) == -1:  # Гарантированно победит Ваня первым ходом
        print(S)  # В ответ возьмём последнее выведенное значение

Ответ: 47