20.01 Теория игр

from functools import lru_cache


@lru_cache(None)
def f(a, b, c):
    if a + b >= 199:
        return 0
    moves = [f(a, b * 2, c)]
    if c == 0:
        moves.append(f(b, a, 1))
    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, 100):
    if f(99, i, 0) == 2:
        print(i)
        break