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

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

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

from functools import lru_cache
 

 
# c = 1 если в прошлый ход меняли кучи местами
 
def moves(h):
 
    a, b, c = h
 
    res = []
 

 
    res.append((a, b * 2, 0))
 
    if c == 0:
 
        res.append((b, a, 1))
 

 
    return tuple(res)
 

 
@lru_cache(None)
 
def f(h):
 
    if sum(h[:2]) >= 199:
 
        return «END»
 
    if any((f(x) == «END») for x in moves(h)):
 
        return «P1»
 
    if all((f(x) == «P1») for x in moves(h)):
 
        return «V1»
 
    if any((f(x) == «V1») for x in moves(h)):
 
        return «P2»
 
    if all((f(x) == «P2» or f(x) == «P1») for x in moves(h)):
 
        return «V2»
 

 
for s in range(1, 100):
 
    h = 99, s, 0
 
    if f(h) == «V2»:
 
        print(s, «V2»)

Ответ: 7 8
Оцените статью
Я решу все!