Задача к ЕГЭ по информатике на тему «Перекладывание камней две кучи» №6

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч два камня или увеличить количество камней в куче в три раза. Например, пусть в одной куче будет $10$ камней, а в другой $8$ камней; такую позицию мы будем обозначать $(10,8)$ . За один ход из позиции $(10,8)$ можно получить любую из четырёх позиций: $(12,8),(10,10),(30,8),(10,24)$ . Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее $43$ .

Победителем считается игрок, сделавший последний ход, то есть первым получивший позицию, в которой в кучах будет $43$ или более камней. В начальный момент в первой куче было $6$ камней, во второй куче $S$ камней, $1 ≤ S ≤ 36.$

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

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

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

Найдем такие $S,$ при которых Петя может выиграть своим первым ходом. Должно выполняться хотя бы одно из двух неравенств: $6⋅3 + S ≥ 43$ или $6+ S ⋅3 ≥ 43$ . То есть Петя может выиграть при $S ≥ 25$ или $S ≥ 13.$ Таким образом, если мы возьмем $S = 12,$ то Петя никак не сможет выиграть первым ходом, но при этом любым своим ходом он создаст выигрышную позицию для Вани, и тогда Ваня уже гарантированно победит своим первым ходом.

Решение БУ

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

Ответ: 12