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

Просмотров 8 Комментарии 0

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

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

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

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

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

Максимальный ход, доступный нам в партии это $∗ 2$ . Выигрыш достигается при 39+ камнях, значит, что область, в которой Петя может выиграть начинается с: $39 --= 19,5 2$

Округляем в бОльшую сторону и получаем $20$ . В отрезке [20;38] Петя побеждает в один ход. Минимальное значение S: $20$ .

Решение БУ

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

Ответ: 20