Задания №19, 20, 21. Теория игр (Одна и две кучи камней)

# === Универсальный шаблон Заданий 19, 20, 21 на Python ===

def moves(h):
    a, b = h
    return [(a + 1, b), (a * 2, b), (a, b + 1), (a, b * 2)]

# Рекурсивная функция: возвращает True, если игрок побеждает за k ходов
def game(h, k):
    if sum(h) >= 77:
        return k % 2 == 0
    if k == 0:
        return False
        
    next_moves = [game(m, k - 1) for m in moves(h)]
    
    # Если ход текущего игрока — достаточно ХОТЯ БЫ ОДНОГО выигрышного хода (any):
    # Если ход соперника — победа должна быть при ЛЮБОМ его ходе (all):
    if (k - 1) % 2 == 0:
        return any(next_moves)
    else:
        return all(next_moves)

print("--- Задание 19 (Ваня выигрывает 1-м ходом, k=2) ---")
# В 19 задаче часто условие: Петя ошибся (any вместо all на 1-м ходу):
for s in range(1, 70):
    if any(sum(m) >= 77 for m in moves((7, s))):
        pass # Петя мог выиграть сразу
    elif any(any(sum(m2) >= 77 for m2 in moves(m1)) for m1 in moves((7, s))):
        print("19:", s)
        break

print("--- Задание 20 (Петя выигрывает 2-м ходом, k=3) ---")
for s in range(1, 70):
    if not game((7, s), 1) and game((7, s), 3):
        print("20:", s)

print("--- Задание 21 (Ваня выигрывает 1-м или 2-м ходом, k=4) ---")
for s in range(1, 70):
    if not game((7, s), 2) and game((7, s), 4):
        print("21:", s)