19.02 Перекладывание камней две кучи

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

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

Решение БУ

from functools import lru_cache


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


# Поиск минимального значения S для выигрыша Вани
for s in range(1, 37):
    if game(6, s) == -1:
        print(s)  # Вывод минимального значения S
        break