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

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

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

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

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

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

Из предыдущей задачи мы знаем, что при значениях $17$ и $18$ Ваня гарантированно победит своим первым ходом. Если после первого хода Пети в куче будет $17$ или $18$ камней, значит, в этой позиции Петя гарантированно победит вторым ходом. Распишем значения и стратегии, при которых Петя победит своим вторым ходом: При $S = 6$ Петя может перейти в позицию $18$ ходом $∗3$ и гарантированно после хода Вани выиграет партию своим вторым ходом.

При $S = 13$ Петя может перейти в позицию $17$ ходом $+ 4$ и гарантированно после хода Вани выиграет партию своим вторым ходом.

При $S = 14$ Петя может перейти в позицию $18$ ходом $+ 4$ и гарантированно после хода Вани выиграет партию своим вторым ходом.

При $S = 15$ Петя может перейти в позицию $17$ ходом $+ 2$ и гарантированно после хода Вани выиграет партию своим вторым ходом.

При $S = 16$ Петя может перейти в позицию $18$ ходом $+ 2$ и гарантированно после хода Вани выиграет партию своим вторым ходом.

В ответ нужно указать два максимальных значениях S. Ответ: $1516$

Решение БУ

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

Ответ: 1516