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)