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

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу $2$ или $4$ камня или увеличить количество камней в куче в три раза. Например, имея кучу из $12$ камней, за один ход можно получить кучу из $14$ , $16$ или $36$ камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней.

Игра завершается в тот момент, когда количество камней в куче становится не менее $55$ . Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет $55$ или больше камней.

В начальный момент в куче было $1 ≤ S ≤ 54$ . Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.

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

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

Для начала найдем значения S, при которых Петя гарантированно побеждает своим первым ходом. Максимальный ход, доступные в партии это $∗ 3$ . Определим минимальное значение, из которого Петя может победить в один ход: $55 = 18,33.. 3$ (округляем в большую сторону) = $19$ . Значения, после которых мы гарантированно можем попасть в область [19;54] – это значения, в которых Ваня побеждает своим первым ходом. Распишем подробно значение и стратегии, в которых Ваня побеждает своим первым ходом:

При $S = 17$ Петя может прийти в три позиции: $19$ , $21$ и $51$ . В любых этих позициях Ваня гарантированно побеждает своим первым ходом.

При $S = 18$ Петя может прийти в три позиции: $20$ , $22$ и $54$ . Так как 20 ⋅3 > 55, » class=»math» src=»/images/inform/reshen/reshen-2105-12.svg» width=»auto»> то Ване уже неважно, какой конкретно ход сделает Петя. </p>
<p class= В ответ нужно указать максимальное значение S, по этой причине ответ $18$ .

Решение БУ

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

Ответ: 18