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

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

Следовательно, минимальные значения , при которых Петя выигрывает своим вторым ходом, это и .

Решение программой
Этот код очень похож на реализацию из задачи 19: он также использует рекурсию для проверки всех возможных ходов (, , с округлением вниз) и определяет выигрышные позиции. Отличие лишь в том, что здесь мы ищем значения , при которых Петя выигрывает своим вторым ходом, проверяя game(S) == 2.

from functools import lru_cache


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


for i in range(22, 1000):
    if game(i) == 2:  # Если в данной позиции возможен выигрыш Пети за два хода
        print(i)