Теория игр — №21

from functools import lru_cache

@lru_cache(None)
def f(s, m):
    if s >= 132: return m % 2 == 0
    if m == 0: return False
    h = [f(s+3, m-1), f(s+6, m-1), f(s*3, m-1)]
    return any(h) if m % 2 != 0 else all(h)

# Ответ на №21
print('#21', min(s for s in range(1, 132) if not f(s, 2) and f(s, 4)))

# Две кучи (если задача с двумя кучами)
@lru_cache(None)
def g(x, y, m):
    if x + y >= 77: return m % 2 == 0
    h = [g(x+3,y,m-1), g(x*3,y,m-1), g(x,y+3,m-1), g(x,y*3,m-1)]
    return any(h) if m % 2 != 0 else all(h)