19.04 Уменьшение количества камней

Решение руками

Неудачный ход – ход при котором игрок мог победить, но отдал победу противнику. Поэтому для начала найдем значения , при которых Петя мог победить за 1 или 2 хода.

Рассмотрим ситуацию, когда Петя сделал один ход. Чтобы получить число 7 есть всего 2 возможных хода: убрать из кучи один камень или убрать из кучи три камня. Для этих ходов подойдут значения и .

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

Рассмотрим . Первым ходом Петя делает неудачный ход – убирает 1 камень, – из этой позиции нельзя победить за один ход, поэтому этот вариант не подходит.

Рассмотрим . Первым ходом Петя делает неудачный ход – убирает 3 камня, – из этой позиции можно победить за один ход, поэтому этот вариант подходит.

Идея решения:

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

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

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

Решение программой

from functools import lru_cache

@lru_cache(None)
def game(heap):  # Функция игры
    if heap <= 7:  # Если камней в кучах стало меньше 7
        return 0  # Прекращаем игру
    moves = [game(heap - 1), game(heap - 3)]  # Генерация всех возможных ходов
    petya_win = [i for i in moves if i <= 0]
    if petya_win: # если в данной позиции есть выигрыш Пети
        return -max(petya_win) + 1
    else: # если в данной позиции выигрыш Вани
        return -max(moves)

for i in range(8, 100):
    if game(i) == 1 or game(i) == 2:  # Если Петя мог победить своим 1ым или 2м ходом

        # Для неудачного хода Пети нужно вручную сделать за него ходы от взятого s
        # и запустить функцию с изменнённым значением кучи, чтобы в хотя бы одном из ходов Петя ошибся.
        # Таким образом, Ваня станет первым ходившим игроком для функции,
        # и в итоге нужно будет получить значение 1 для победы Вани первым ходом после неудачного хода Пети.

        vanya_win = False  # Переменная-флаг, отвечающая за победу Вани (изначально Ваня не побеждает)
        if game(i - 1) == 1:  # Если при ходе -1 в итоге победит Ваня
            vanya_win = True
        if game(i - 3) == 1:  # Если при ходе -3 в итоге победит Ваня
            vanya_win = True

        if vanya_win:  # Если в итоге Ваня победил
            print(i)