Задача к ЕГЭ по информатике на тему «Теория игр» №3

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

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

– Петя не может выиграть за один ход

– Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.

В ответе запишите числа в порядке возрастания без пробелов и знаков препинаний.

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

Из предыдущей задачи мы знаем, что в отрезке [61;70] Петя гарантированно выигрывает своим первым ходом. В значении 60 Ваня гарантированно выигрывает своим первым ходом после любого хода Пети. Значит, что если после первого хода Пети в куче станет 60 камней, значит, он гарантированно выиграет в партии своим вторым ходом. Распишем из каких значений за один ход можно попасть в 60:

Если $S = 59$ , то Пете достаточно прибавить к куче $1$ камень. Тогда Ваня сможет увеличить количество камней либо до $61$ , либо до $70$ , откуда Пете достаточно прибавить $10$ к любому из этих значений.

Если $S = 50$ , то Пете достаточно прибавить к куче $10$ камней. Далее аналогично предыдущим действиям.

Решение БУ

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) == 2: # если в данной позиции Петя побеждает вторым ходом
        print(i)

Ответ: 5059