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

from functools import lru_cache

LIMIT = 118     # игра заканчивается, когда суммарно не меньше 118 камней
PLUS = 5        # «добавить в одну из куч 5 камней»
MULT = 2        # «увеличить одну из куч в 2 раза»
START = 11      # камней в первой куче


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 win(pos, k):
    """Успевает ли игрок, чей сейчас ход, выиграть за k своих ходов."""
    if k == 0:
        return False
    for q in moves(pos):
        if is_over(q):
            return True                  # выиграл этим ходом
        # ход хорош, если Ваня не выигрывает сразу и мы успеваем за k - 1 ход
        if all(not is_over(r) and win(r, k - 1) for r in moves(q)):
            return True
    return False


found = []
for s in range(1, 107):
    if win((START, s), 2) and not win((START, s), 1):
        found.append(s)
        if len(found) == 2:
            break

print(found[0], found[1])

from functools import lru_cache

LIMIT = 87      # игра заканчивается, когда камней не меньше 87
PLUS = 5        # «добавить в кучу 5 камней»
MULT = 3        # «увеличить количество камней в куче в 3 раза»


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


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


@lru_cache(maxsize=None)
def win(pos, k):
    """Успевает ли игрок, чей сейчас ход, выиграть за k своих ходов."""
    if k == 0:
        return False
    for q in moves(pos):
        if is_over(q):
            return True                  # выиграл этим ходом
        # ход хорош, если Ваня не выигрывает сразу и мы успеваем за k - 1 ход
        if all(not is_over(r) and win(r, k - 1) for r in moves(q)):
            return True
    return False


found = []
for s in range(1, 87):
    if win(s, 2) and not win(s, 1):
        found.append(s)
        if len(found) == 2:
            break

print(found[0], found[1])

from functools import lru_cache

LIMIT = 47      # игра заканчивается, когда камней не больше 47
MIN1 = 3        # «убрать из кучи 3 камня»
MIN2 = 7        # «убрать из кучи 7 камней»
DIV = 3         # «уменьшить в 3 раза», деление с округлением вниз


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


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


@lru_cache(maxsize=None)
def win(pos, k):
    """Успевает ли игрок, чей сейчас ход, выиграть за k своих ходов."""
    if k == 0:
        return False
    for q in moves(pos):
        if is_over(q):
            return True                  # выиграл этим ходом
        # ход хорош, если Ваня не выигрывает сразу и мы успеваем за k - 1 ход
        if all(not is_over(r) and win(r, k - 1) for r in moves(q)):
            return True
    return False


found = []
for s in range(48, 500):
    if win(s, 2) and not win(s, 1):
        found.append(s)
        if len(found) == 2:
            break

print(found[0], found[1])