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

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

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

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

В начальный момент в куче было $S$ камней, $1 ≤ S ≤ 70$ .

Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.

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

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

Максимальный ход, доступный нам в партии это +10. Значит, в отрезке [61;70] Петя гарантированно побеждает своим первым ходом.

Если $S = 61$ , то Пете достаточно прибавить к куче $10$ камней.

Если $S = 70$ , то Пете достаточно прибавить к куче $1$ камень.

Решение БУ

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

Ответ: 6170