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

Два игрока, Оливье и Крабовый, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Оливье. За один ход игрок может убрать из кучи один камень или убрать из кучи два камня. Например, имея кучу из $10$ камней, за один ход можно получить кучу из $9$ или $8$ камней. Чтобы делать ходы, у каждого игрока есть неограниченное количество камней. Игра завершается в тот момент, когда количество камней в куче становится не более $34$ .

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

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

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

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

Найдем такие $S$ , при которых Оливье может выиграть своим первым ходом. Должно выполняться неравенство: $S − 2 ≤ 34$ . То есть Оливье может выиграть при $S ≤ 36$ . Таким образом, если мы возьмем $S = 37$ то Оливье никак не сможет выиграть первым ходом, но при этом любым своим ходом он создаст выигрышную позицию для Крабового, и тогда Крабовый уже гарантированно победит своим первым ходом.

Решение БУ

#Петя - Оливье
#Ваня - Крабовый

from functools import lru_cache
@lru_cache(None)
def game(first_heap): # функция игры
    if first_heap <= 34: # если камней в куче стало меньше 34
        return 0 # прекращаем игру
    moves = [game(first_heap-1),game(first_heap-2)] # прописываем ходы возможные в партии
    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(36,100):
    if game(i) == -1: # если в данной позиции Ваня побеждает первым ходом
        print(i)

Решение АР

from functools import lru_cache


def moves(h):
    return h - 1, h - 2


@lru_cache(None)
def f(h):
    if h <= 34:
        return ’END’
    if any(f(x) == ’END’ for x in moves(h)):
        return ’WIN1’
    if all(f(x) == ’WIN1’ for x in moves(h)):
        return ’LOSE1’


for i in range(36, 100):
    if f(i) == ’LOSE1’:
        print(i)

Ответ: 37