Задание 21 ЕГЭ по информатике 2027: теория игр: дерево игры

from functools import lru_cache

LIMIT = 120   # игра заканчивается при сумме не менее 120
PLUS = 5      # добавление камней
MULT = 2      # увеличение кучи
FIRST = 14    # камней в первой куче в начале


def moves(pos):
    """Позиции, которые можно получить из pos одним ходом."""
    a, b = pos
    return ((a + PLUS, b), (a, b + PLUS), (a * MULT, b), (a, b * MULT))


def is_over(pos):
    """Игра закончена: в двух кучах суммарно не меньше LIMIT камней."""
    return pos[0] + pos[1] >= LIMIT


@lru_cache(maxsize=None)
def wins_first(pos):
    """Игрок, чей ход, выигрывает своим первым ходом."""
    return any(is_over(q) for q in moves(pos))


@lru_cache(maxsize=None)
def wins_second(pos):
    """Игрок, чей ход, выигрывает своим вторым ходом (первым — не может)."""
    if wins_first(pos):
        return False
    for q in moves(pos):
        if not is_over(q) and all(not is_over(r) and wins_first(r) for r in moves(q)):
            return True
    return False


for s in range(1, 106):
    pos = (FIRST, s)
    if wins_first(pos):
        continue  # Петя выигрывает сразу, случай не подходит
    after = moves(pos)
    if all(not is_over(q) and (wins_first(q) or wins_second(q)) for q in after) \
            and any(not wins_first(q) for q in after):
        print(s)
        break

from functools import lru_cache

LIMIT = 93   # игра заканчивается при 93 камнях и более
PLUS = 3     # добавление камней
MULT = 3     # увеличение кучи


def moves(pos):
    """Количества камней, которые можно получить одним ходом."""
    return (pos + PLUS, pos * MULT)


def is_over(pos):
    """Игра закончена: в куче не меньше LIMIT камней."""
    return pos >= LIMIT


@lru_cache(maxsize=None)
def wins_first(pos):
    """Игрок, чей ход, выигрывает своим первым ходом."""
    return any(is_over(q) for q in moves(pos))


@lru_cache(maxsize=None)
def wins_second(pos):
    """Игрок, чей ход, выигрывает своим вторым ходом (первым — не может)."""
    if wins_first(pos):
        return False
    for q in moves(pos):
        if not is_over(q) and all(not is_over(r) and wins_first(r) for r in moves(q)):
            return True
    return False


for s in range(1, LIMIT):
    if wins_first(s):
        continue  # Петя выигрывает сразу, случай не подходит
    after = moves(s)
    if all(not is_over(q) and (wins_first(q) or wins_second(q)) for q in after) \
            and any(not wins_first(q) for q in after):
        print(s)
        break

from functools import lru_cache

LIMIT = 28    # игра заканчивается при 28 камнях и менее
MINUS1 = 3    # ход «убрать камни»
MINUS2 = 7    # второй такой ход
DIV = 4       # ход «уменьшить кучу в 4 раза»


def moves(pos):
    """Количества камней, которые можно получить одним ходом."""
    return (pos - MINUS1, pos - MINUS2, pos // DIV)


def is_over(pos):
    """Игра закончена: в куче не больше LIMIT камней."""
    return pos <= LIMIT


@lru_cache(maxsize=None)
def wins_first(pos):
    """Игрок, чей ход, выигрывает своим первым ходом."""
    return any(is_over(q) for q in moves(pos))


@lru_cache(maxsize=None)
def wins_second(pos):
    """Игрок, чей ход, выигрывает своим вторым ходом (первым — не может)."""
    if wins_first(pos):
        return False
    for q in moves(pos):
        if not is_over(q) and all(not is_over(r) and wins_first(r) for r in moves(q)):
            return True
    return False


for s in range(LIMIT + 1, LIMIT * 20):
    if wins_first(s):
        continue  # Петя выигрывает сразу, случай не подходит
    after = moves(s)
    if all(not is_over(q) and (wins_first(q) or wins_second(q)) for q in after) \
            and any(not wins_first(q) for q in after):
        print(s)
        break