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

Позицией называется вся информация о текущем состоянии игры в момент, когда один из игроков должен сделать ход (например, размер кучи камней или пара размеров двух куч). Чтобы отвечать на задания 19–21, удобно раскрасить позиции по тому, за сколько ходов и кто в них побеждает при правильной игре. Три обозначения ниже — не официальная терминология ФИПИ, а рабочий язык, которым удобно пользоваться при разборе: они не встретятся в тексте самого задания, но избавляют от путаницы в рассуждениях.

В1 — «выигрыш в один ход»

Позиция $X$ относится к В1, если игрок, которому сейчас ходить, может каким-то одним ходом сразу завершить игру (довести сумму, произведение или значение кучи до порога). Достаточно, чтобы подходил хотя бы один из возможных ходов — искать оптимальный ход дальше не нужно, игра на этом закончится.

П1 — «проигрыш через один ход соперника»

Позиция $X$ относится к П1, если одновременно выполнены два условия: сам игрок из неё выиграть за один ход не может (то есть $X$ не в В1), и каждый его возможный ход уводит соперника в позицию класса В1. Иначе говоря, из П1 нет спасения: что ни делай, соперник следующим ходом выигрывает.

В2 — «выигрыш за два хода при любом ответе соперника»

Позиция $X$ относится к В2, если сам игрок не может выиграть за один ход (не в В1), но у него есть хотя бы один ход, уводящий соперника в позицию класса П1. Дальше рассуждение простое: соперник оказался в П1, значит, он сам не выиграет следующим ходом, а любой его ход отправит игру обратно в позицию В1 — но теперь ходить в этой позиции будет уже исходный игрок, и он тут же выигрывает.

Обратите внимание на порядок кванторов, из-за которого чаще всего теряют баллы: в П1 условие «каждый ход ведёт в В1» — это квантор «для всех» (по ходам Вани), а в В2 условие «есть ход в П1» — это квантор «существует» (по ходам Пети). Перепутать их местами — значит посчитать совсем другое множество позиций.

Прежде чем считать программой, полезно один раз построить дерево вручную — так видно, откуда берутся кванторы «для всех» и «существует». Возьмём упрощённую версию реальной игры: одна куча камней, за ход можно добавить один камень или удвоить кучу, игра заканчивается, когда в куче становится 8 или больше камней. Проверим стартовое значение $S = 2$.

Петя стоит в позиции 2. У него два хода: $2 \to 3$ (плюс камень) и $2 \to 4$ (удвоение). Разбираем оба, потому что заранее неизвестно, какой из них выигрышный.

Петя: S = 2  (не В1: 2→3 и 2→4, обе < 8)

Ветка А. Петя ходит 2 → 4
  Ваня: S = 4  — это В1 для Вани! 4 → 8, Ваня выигрывает.
  Ветка А не подходит: Петя своим первым ходом отдаёт победу Ване.

Ветка Б. Петя ходит 2 → 3
  Ваня: S = 3  (не В1: 3→4 и 3→6, обе < 8)
  Ваня вынужден выбрать один из двух ходов:

    Ваня 3 → 4
      Петя: S = 4  — это В1 для Пети! 4 → 8, Петя выигрывает 2-м ходом.

    Ваня 3 → 6
      Петя: S = 6  — это тоже В1 для Пети! 6 → 12 ≥ 8, Петя выигрывает.

  Оба ответа Вани из позиции 3 отправляют игру в В1 для Пети.
  Значит, S = 3 — позиция П1, а ход 2 → 3 — выигрышный первый ход Пети.

Итог: при $S = 2$ у Пети есть ход ($2 \to 3$), после которого он не выигрывает сразу (условие «не может выиграть за один ход» выполнено), но гарантированно выигрывает вторым ходом при любом ответе Вани — переберите оба варианта Вани, оба ведут к победе Пети. Значит, $S = 2$ — позиция класса В2, то есть годится в ответ задания 20 в этой упрощённой игре.

Ключевая ошибка, которую дерево наглядно показывает: если бы Петя выбрал ход $2 \to 4$ вместо $2 \to 3$, он бы сразу проиграл — Ваня удвоил бы кучу и выиграл первым же ходом. Это значит, что для проверки условия В2 достаточно найти один подходящий ход Пети — неудачные ходы просто отбрасываются, они не мешают позиции быть выигрышной.

На КЕГЭ доступна среда программирования, а перебор S руками для реальных порогов (десятки и сотни камней) практически невозможен за 7 минут. Ниже — рабочий решатель, написанный и проверенный на примерах из открытого банка ФИПИ ниже в статье. Он строит одну функцию $\text{can\_win\_in\_at\_most}(a, b, k)$ — «может ли игрок, которому сейчас ходить, гарантированно закончить игру не более чем за $k$ своих ходов» — и вызывает её с $k = 1$ (это проверка В1) и с $k = 2$ (это проверка «В1 или В2» вместе).

from functools import lru_cache

THRESHOLD = 59
FIRST_PILE = 5
MAX_S = 53


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


def is_finished(a, b):
    return a + b >= THRESHOLD


@lru_cache(maxsize=None)
def can_win_in_at_most(a, b, k):
    if k <= 0:
        return False
    successors = moves(a, b)
    if any(is_finished(x, y) for x, y in successors):
        return True
    if k == 1:
        return False
    for a1, b1 in successors:
        replies = moves(a1, b1)
        if all(
            not is_finished(x, y) and can_win_in_at_most(x, y, k - 1)
            for x, y in replies
        ):
            return True
    return False


def has_petya_strategy(s):
    wins_in_two = can_win_in_at_most(FIRST_PILE, s, 2)
    wins_in_one = can_win_in_at_most(FIRST_PILE, s, 1)
    return wins_in_two and not wins_in_one


answer = sorted(s for s in range(1, MAX_S + 1) if has_petya_strategy(s))
print(answer[:2])

Логика функции повторяет теорию дословно. Сначала проверяем, нет ли у мовера хода, сразу заканчивающего игру (это и есть проверка В1 — условие $k = 1$). Если её нет и $k \geq 2$, перебираем ходы мовера в нетерминальные позиции и для каждой смотрим на все ответы соперника: если каждый ответ либо сам не заканчивает игру, либо заканчивается тем, что мовер выигрывает в оставшиеся $k - 1$ ходов, — эта позиция мовера подходит. $\text{lru\_cache}$ — это и есть мемоизация: каждая пара (позиция, k) считается ровно один раз, а не пересчитывается заново при каждом вызове.

Итоговое условие задания — «не В1, но В-не-более-чем-2» — это и есть $\text{can\_win\_in\_at\_most}(S, 2)\ \text{и не}\ \text{can\_win\_in\_at\_most}(S, 1)$. Запустите код для приведённого выше $\text{THRESHOLD} = 59$, $\text{FIRST\_PILE} = 5$ — он печатает $[24, 26]$, это ответ реального задания банка ФИПИ, разобранного дальше в статье. Чтобы решить игру с одной кучей вместо двух, замените функции $\text{moves}$ и $\text{is\_finished}$ так, чтобы они принимали одно число вместо пары.

Множество S, удовлетворяющих условию «не В1, но В2», в реальных заданиях банка почти никогда не пусто и почти никогда не состоит из одного числа — обычно таких S несколько подряд или через один-два шага (проверьте это сами: выведите не$\text{answer[:2]}$, а весь список $\text{answer}$ для примеров ниже — в банке встречаются списки из 4–6 и более подходящих значений). Формулировка ФИПИ каждый раз просит только два наименьших — не потому что их всего два, а чтобы ответ был однозначным и умещался в две ячейки бланка.

Отсюда прямое следствие для программы: нельзя останавливать перебор на первых двух найденных S без проверки, что список отсортирован по возрастанию, и без уверенности, что перебор идёт именно с $S = 1$, а не с какого-то произвольного места. В решателе выше это обеспечено конструкцией $\text{range}(1,\ \text{MAX\_S} + 1)$ — перебор всегда начинается с единицы, а Python сохраняет порядок элементов при построении списка через $\text{sorted}(...)$, поэтому $\text{answer[0]}$ гарантированно меньше $\text{answer[1]}$.

Записывать ответ нужно так же, как его печатает программа: сначала меньшее число, затем большее, каждое — в свою ячейку таблицы бланка. Менять их местами, даже если оба числа правильные, нельзя — задание считается выполненным верно только если ответ «полностью совпадает с эталоном», а эталон зафиксирован в порядке возрастания.

День 1–2: разберите тренировочный пример из этой статьи (одна куча, порог 8) руками, без программы — постройте дерево целиком и убедитесь, что понимаете, откуда берутся кванторы «для всех» и «существует» в определениях В1, П1 и В2. День 3–4: наберите Python-решатель из статьи, запустите его на примерах 1 и 2 и сверьте со своими ответами. День 5–7: возьмите задание 19 своего варианта, прочитайте условие игры и убедитесь, что понимаете все параметры (сколько куч, какие ходы, чем считается порог) — задание 20 без этого решить нельзя.

День 1–3: прорешайте несколько заданий 20 с разными условиями окончания игры — по сумме куч, по произведению, по одной куче — каждый раз переписывая только функции $\text{moves}$ и $\text{is\_finished}$, а не решатель целиком. День 4–5: тренируйтесь быстро выделять в длинной формулировке три обязательных условия («есть стратегия», «не за один ход», «за два хода при любом ответе») и сразу переводить их в вызовы $\text{can\_win\_in\_at\_most}$. День 6–7: решайте задание 20 на время — не больше 7 минут вместе с набором кода, и проверяйте себя в тренажёре на заданиях из банка ФИПИ.