20.01 Теория игр

from functools import lru_cache


@lru_cache(None)
def f(a, b, c=0):
    if a * b >= 1056:
        return 0
    if c > 4:
        return -10 ** 10
    moves = [f(a + 1, b, c + 1), f(a * 4, b, c + 1), f(a, b + 1, c + 1), f(a, b * 4, c + 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, 132):
    if f(8, i) == 2:
        print(i)