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

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу три камня, добавить четыре камня или увеличить количество камней в куче в три раза. При этом не разрешается делать ход, после которого количество камней в куче будет делиться на 2. Игра завершается, когда количество камней в куче становится не менее 180. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 180 или больше камней. В начальный момент в куче было S камней, 1 $≤$ S $≤$ 179, S не делится на 2.

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

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

Для начала определим какие ходы в каких ситуациях мы можем совершать. Изначальное значение S всегда нечётное, также после ходов мы должны получать нечётные значения, значит, в данной игре мы можем использовать только $+ 4$ , $∗ 3$ ходы. Так как, нечётное * нечётное = нечётное число и нечётное + чётное = нечётное число. Теперь определим при каких значениях первым ходом побеждает Петя. Максимальный ход, который мы можем совершить это $∗3$ . Минимальное значение, при котором Петя побеждает своим первым ходом равняется: $180 = 60 3$

Поскольку данное значение чётное, оно нам не подходит. Тогда берём следующее значение $61$ и оно уже нам подходит. Получается, что все нечётные значения в отрезке [61;179] — это значения, в которых Петя побеждает своим первым ходом.

Определим значения, при которых Ваня побеждает своим первым ходом. Значение, из которого ВСЕ ходы ведут в вышеописанный отрезок – это значение, в котором Ваня выигрывает своим первым ходом. Распишем значения и стратегии, при которых Ваня побеждает первым ходом:

$S = 57$ . Петя может увеличить количество камней до $61$ ходом $+ 4$ или до $171$ ходом $∗3$ . В обоих случаях Ване не составит труда завершить партию следующим ходом.

$S = 59$ . Петя может увеличить количество камней до $63$ ходом $+ 4$ или до $177$ ходом $∗3$ . В обоих случаях Ване не составит труда завершить партию следующим ходом.

В ответ нужно указать наибольшее значение S. Ответ: $59$

Программная реализация

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

В результате программы на экран будет выведены числа 57 и 59. Наибольшим является число 59.

Ответ: 59