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

Задание 20 ЕГЭ по информатике (КЕГЭ) — средняя часть блока «игра двух игроков», который тянется через задания 19, 20 и 21 на одном общем условии. Это задание повышенного уровня сложности, за него дают 1 первичный балл, а форма ответа — два числа в двух ячейках таблицы, записанные в порядке возрастания. По обобщённому плану ФИПИ на него отводится около 8 минут. Раздел кодификатора — «Теоретические основы информатики», КЭС 2.15 («Анализ алгоритма логической игры»), проверяемое требование — 2.1. В статье — разбор длинной формулировки задания по частям, понятия позиций В1, П1 и В2, рабочий Python-решатель с мемоизацией, разбор дерева игры руками на маленьких числах, три реальных задания из открытого банка ФИПИ и список типичных ловушек. Потренироваться можно на реальных заданиях 20 ЕГЭ по информатике онлайн — с мгновенной проверкой ответа.

Что проверяет задание 20 ЕГЭ по информатике

Задания 19, 20 и 21 — единственный на всём КЕГЭ блок с общим стимулом: условие игры полностью описано один раз, в задании 19, а задания 20 и 21 к нему только отсылают («Для игры, описанной в задании 19…»). Своей копии условия у задания 20 нет. Все три задания используют один и тот же раздел кодификатора — «Анализ алгоритма логической игры», КЭС 2.15, проверяемое требование 2.1 — но проверяют разные умения и оцениваются независимо, по 1 баллу каждое:

Три задания одного блока:

Задание 19 (базовый уровень) — найти одно конкретное значение параметра S, при котором выигрывает тот или иной игрок при заданном сценарии первых ходов;
Задание 20 (повышенный уровень, эта статья) — найти два значения S, при которых у Пети есть выигрышная стратегия ровно определённого вида: не выигрывает за один ход, но гарантированно выигрывает за два;
Задание 21 (высокий уровень) — построить дерево игры и найти одно минимальное значение S, при котором выигрышная стратегия есть уже у Вани, второго игрока, а не у Пети.

Формулировка задания 20 без исключений содержит одну и ту же логическую конструкцию: у игрока Пети есть выигрышная стратегия, причём одновременно выполняются два условия — Петя не может выиграть за один ход, но может выиграть своим вторым ходом, независимо от того, как отвечает Ваня. Нужно найти два наименьших S с таким свойством и записать их в порядке возрастания. Дальше в статье эта фраза разобрана по частям — она короткая, но в ней три вложенных условия, и потерять одно из них означает потерять весь балл.

Проекты КИМ-2027 ФИПИ публикует в конце августа 2026 года, финальные версии — в ноябре. Все цифры в статье приведены по действующей спецификации ФИПИ 2026 года; структура работы не менялась с 2025 года.

Параметр	Значение
Максимальный балл	1 первичный. Частичного зачёта нет: ответ либо полностью совпадает с эталоном, либо 0 баллов
Уровень сложности	Повышенный (П)
Раздел кодификатора	Теоретические основы информатики; КЭС 2.15 «Анализ алгоритма логической игры»; требование 2.1
Форма ответа	Два числа в двух ячейках таблицы бланка, записанные в порядке возрастания
Файл, спец. ПО	Не требуются
Рекомендуемое время	8 минут (примерное время выполнения задания по обобщённому плану ФИПИ)
Связанные задания	Задание 19 (то же условие игры, одно значение S) и задание 21 (то же условие игры, одно значение S, но для Вани)

Тренируйтесь на реальных играх из банка ФИПИ

Задания ЕГЭ по информатике из открытого банка ФИПИ с мгновенной проверкой ответа. Решаем, ошибаемся, разбираем — бесплатно.

Решать задание 20

Как выглядит формулировка

Меняются игра, число куч, правило хода и порог окончания игры, но сама фраза-вопрос задания 20 почти дословно повторяется из варианта в вариант. Вот формулировки из реальных заданий открытого банка ФИПИ:

«Для игры, описанной выше, найдите два наименьших значения S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия: — Петя не может выиграть за один ход; — Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня. Найденные значения запишите в ответе в порядке возрастания.»
«Для игры, описанной в предыдущем задании, найдите два таких значения S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия: …» — в некоторых заданиях банка ссылка сформулирована как «в предыдущем задании», а не «в задании 19», но имеется в виду ровно то же условие блока.

Как читать эту формулировку по порядку. В ней зашито не одно, а три требования, и все три обязательны одновременно:

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

Только S, прошедшие все три фильтра сразу, идут в ответ. Их обычно несколько (иногда бесконечно много, если S не ограничено сверху вариантом задачи), а спрашивают — два наименьших.

Как записывается ответ. Ответ на задание 20 — это два числа в двух ячейках таблицы бланка ответов, и они обязаны идти в порядке возрастания: сначала меньшее значение S, затем большее. Это не рекомендация, а прямое требование инструкции к заданию — «найденные значения запишите в ответе в порядке возрастания». Частичного зачёта, в отличие от заданий 26 и 27, здесь нет: если числа стоят не в том порядке или найдено только одно значение из двух, за задание ставится 0 баллов, а не половина.

Теория: всё, что нужно для задания 20

Три класса позиций: В1, П1, В2

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

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

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

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

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

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

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

Ответ задания 20 — это в точности S, начальная позиция при которых относится к классу В2 (для игрока Пети, который ходит первым). Три условия из формулировки — «есть выигрышная стратегия», «не выигрывает за один ход», «выигрывает вторым ходом при любом ответе Вани» — это ровно определение В2, разложенное на слова.

Обратите внимание на порядок кванторов, из-за которого чаще всего теряют баллы: в П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 достаточно найти один подходящий ход Пети — неудачные ходы просто отбрасываются, они не мешают позиции быть выигрышной.

Рабочий решатель на Python

На КЕГЭ доступна среда программирования, а перебор S руками для реальных порогов (десятки и сотни камней) практически невозможен за 8 минут. Ниже — рабочий решатель, написанный и проверенный на примерах из открытого банка ФИПИ ниже в статье. Он строит одну функцию $\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]}$ .

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

Алгоритм решения

Прочитайте условие игры в задании 19 (задание 20 своей копии условия не содержит) и выпишите: сколько куч, какие ходы разрешены, от чего считается порог окончания игры (сумма, произведение или значение одной кучи) и чему равен сам порог.
Выпишите фиксированные начальные значения куч из условия задания 20 (например, «в первой куче было пять камней») и диапазон переменной $S$ .
Определите функцию $\text{moves}$ (все ходы из позиции) и функцию $\text{is\_finished}$ (проверка, что порог достигнут) строго по тексту условия — это единственное место, где различаются варианты банка.
Реализуйте рекурсивную функцию $\text{can\_win\_in\_at\_most}(state, k)$ с мемоизацией, как показано в блоке выше.
Переберите все допустимые S по возрастанию и отберите те, для которых $\text{can\_win\_in\_at\_most}(S, 2)$ истинно, а $\text{can\_win\_in\_at\_most}(S, 1)$ — ложно.
Возьмите два первых элемента получившегося списка — он уже отсортирован по возрастанию, если перебор шёл от меньших S к бóльшим.
Запишите оба числа в бланк в двух ячейках в том порядке, в котором их вывела программа: меньшее — в первую ячейку, большее — во вторую.

Проверьте решатель на своём варианте

У каждого варианта задания 20 свои числа: другая куча, другой порог, другое начальное значение. Тренируйтесь на реальных заданиях банка ФИПИ и проверяйте ответ мгновенно.

Перейти к практике

Примеры с разбором

Ниже — три реальных задания открытого банка ФИПИ. Каждый ответ получен и перепроверен запуском Python-решателя из блока выше (с заменой $\text{THRESHOLD}$ , $\text{FIRST\_PILE}$ и, где нужно, условия окончания игры на произведение вместо суммы), а не взят из текстового разбора банка.

Пример 1. Одна куча камней, порог 29

Условие (реальное задание из открытого банка ФИПИ):

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один камень или увеличить количество камней в куче в два раза. Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней. Игра завершается в тот момент, когда количество камней в куче становится не менее 29. Победителем считается игрок, сделавший последний ход, т. е. первым получивший кучу, в которой будет 29 или больше камней. В начальный момент в куче было S камней, 1 ≤ S ≤ 28. Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Для игры, описанной выше, найдите два таких значения S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия: — Петя не может выиграть за один ход; — Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня. Найденные значения запишите в ответе в порядке возрастания.

Решение:

Здесь одна куча, ход — $v \to v+1$ или $v \to 2v$ , порог — 29. Классифицируем все значения от 1 до 28 функциями решателя. Позиция В1 — это любое $v \geq 15$ : при таком v удвоение сразу даёт $2v \geq 30 \geq 29$ . Значит, при $v \leq 14$ выиграть за один ход нельзя.

Проверяем П1 для $v = 14$ : оба хода из 14 — это 15 и 28, а оба они $\geq 15$ , то есть оба относятся к В1. Значит, 14 — позиция П1: не выиграть сразу, и любой ход отдаёт победу сопернику следующим ходом. Это единственная П1-позиция для этой игры.

Теперь ищем S, из которых есть ход в 14. Удвоение $7 \to 14$ и добавление камня $13 \to 14$ — оба варианта подходят, а сами 7 и 13 не являются В1 (их ходы — 8, 14 и 14, 26 — все меньше 29). Других способов попасть в 14 за один ход нет.

Ответ: 7 13. Здравый смысл: 7 и 13 — два наименьших значения, оба ведут ровно в единственную П1-позицию, порядок возрастания уже соблюдён.

Пример 2. Две кучи, порог по сумме

Условие (реальное задание из открытого банка ФИПИ):

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч (по своему выбору) один камень или увеличить количество камней в куче в два раза. Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней. Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 59. Победителем считается игрок, сделавший последний ход, т. е. первым получивший такую позицию, при которой в кучах оказывается 59 или больше камней. В начальный момент в первой куче было пять камней, во второй куче — S камней; 1 ≤ S ≤ 53. Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Для игры, описанной выше, найдите два наименьших значения S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия: — Петя не может выиграть за один ход; — Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня. Найденные значения запишите в ответе в порядке возрастания.

Решение:

Позиция теперь — пара (первая куча, вторая куча), стартует Петя из (5, S). Ходов у него четыре: $(a{+}1,b)$ , $(2a,b)$ , $(a,b{+}1)$ , $(a,2b)$ , а условие окончания — сумма куч $\geq 59$ . Запускаем решатель с этими правилами и $\text{FIRST\_PILE} = 5$ , $\text{THRESHOLD} = 59$ .

При $S = 24$ Петя не может выиграть за один ход (все четыре хода из (5, 24) дают суммы 30, 34, 30, 53 — все меньше 59), но ход $5 \to 10$ (удвоение первой кучи) переводит игру в позицию (10, 24), которая оказывается П1: у Вани там четыре хода — (11,24), (20,24), (10,25), (10,48), и из каждой Петя тут же выигрывает одним ходом (например, из (10,48) ходом $10 \to 11$ , сумма станет 59).

При $S = 26$ ход $5 \to 6$ (плюс камень к первой куче) переводит игру в (6, 26) — тоже П1-позиция: любой из четырёх ответов Вани снова отдаёт Пете немедленную победу.

Ответ: 24 26. Совпадает с эталоном банка. Здравый смысл: оба значения не позволяют выиграть сразу (иначе задание было бы бессмысленным), а разница между ними всего 2 — характерная плотность для игр с ходом «плюс один камень».

Пример 3. Две кучи, порог по произведению

Условие (реальное задание из открытого банка ФИПИ):

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч (по своему выбору) один камень либо увеличить количество камней в куче в два раза. Например, пусть в одной куче 10 камней, а в другой 7 камней; такую позицию в игре будем обозначать (10, 7). Тогда за один ход можно получить любую из четырёх позиций: (11, 7), (20, 7), (10, 8), (10, 14). Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней. Игра завершается в тот момент, когда произведение количеств камней в кучах становится не менее 144. Победителем считается игрок, сделавший последний ход, т. е. первым получивший такую позицию, что произведение количеств камней в кучах будет 144 или больше. В начальный момент в первой куче было два камня, во второй куче — S камней; 1 ≤ S ≤ 141. Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Для игры, описанной выше, найдите два наименьших значения S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия: — Петя не может выиграть за один ход; — Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня. Найденные значения запишите в ответе в порядке возрастания.

Решение:

Единственное отличие от примера 2 — условие окончания игры: вместо суммы теперь произведение куч $a \cdot b \geq 144$ . В решателе меняется только функция $\text{is\_finished}$ , вся остальная логика (В1, П1, В2, мемоизация) остаётся без изменений — это и есть главное преимущество решателя на функциях, а не на жёстко прописанном переборе.

Старт — (2, S). При $S = 17$ ход $2 \to 4$ (удвоение первой кучи) даёт (4, 17): произведение 68, до 144 не дотягивает. У Вани отсюда четыре хода — (5,17)=85, (8,17)=136, (4,18)=72, (4,34)=136 — ни один не достигает 144, игра продолжается. Но из каждой из этих четырёх позиций Петя тут же выигрывает: из (5,17) удвоением второй кучи — 5·34=170; из (8,17) добавлением камня — 9·17=153; из (4,18) удвоением первой кучи — 8·18=144; из (4,34) добавлением камня — 5·34=170. Все четыре ветки Вани заканчиваются немедленной победой Пети, значит (4, 17) — позиция П1.

При $S = 23$ ход $2 \to 3$ (плюс камень) даёт (3, 23) — тоже позицию П1.

Ответ: 17 23. Совпадает с эталоном банка. Этот пример — лучшая иллюстрация того, зачем в задании 20 нужна именно программа, а не рассуждение руками: как только в игре появляется произведение вместо суммы, количество возможных позиций и ветвлений растёт быстро, и без перебора без ошибок не обойтись.

Типичные ошибки и ловушки

Перепутали «за один ход» и «не более чем за два хода»

Условие «может выиграть своим вторым ходом» не означает «выигрывает либо за один ход, либо за два» — оно означает строго В2 при обязательном «не может выиграть за один ход». Если запрограммировать только $\text{can\_win\_in\_at\_most}(S, 2)$ без проверки $\text{not}\ \text{can\_win\_in\_at\_most}(S, 1)$ , в список попадут и все В1-позиции — лишние значения испортят ответ.

Взяли первые два выигрышных S без условия «не может выиграть первым ходом»

Соблазн — найти любые два наименьших S, при которых «у Пети есть выигрышная стратегия», и остановиться. Но выигрышная стратегия есть почти у всех достаточно больших S, включая те, где Петя выигрывает вообще одним ходом. В ответ идут только те S, что прошли все три условия формулировки, а не только первое.

Забыли, что ответ должен быть отсортирован по возрастанию

Даже если оба числа найдены верно, но записаны не в том порядке (например, сначала большее, потом меньшее), задание оценивается в 0 баллов — «полностью совпадает с эталоном» означает совпадение вплоть до порядка. Частичного зачёта, как в заданиях 26 и 27, здесь нет.

Считали условие окончания игры «на глаз»

Порог может считаться по сумме куч, по произведению или просто по одной куче — это меняет функцию $\text{is\_finished}$ целиком. Спутать сумму с произведением — значит решить совершенно другую игру и получить ответ, который не совпадёт с эталоном ни в одной цифре.

Не проверили, что позиция-цель сама не терминальна

При проверке П1 нужно смотреть только на ходы соперника, не заканчивающие игру немедленно. Если соперник может завершить игру своим ходом из проверяемой позиции, эта позиция П1-позицией не является — соперник выигрывает сам, а не «уступает ход» проверяемому игроку.

Искали позицию, из которой Петя выигрывает при любом своём ходе, а не хотя бы при одном

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

Забыли, что своей копии условия у задания 20 нет

Числа хода — сколько куч, какие операции разрешены, чем считается порог — берутся из формулировки задания 19 того же варианта, а не придумываются заново. Если решать задание 20 в отрыве от задания 19, легко перепутать правила игры одного варианта с правилами другого.

Как задание 20 связано с остальным экзаменом

Всего в КИМ ЕГЭ по информатике 27 заданий, все с кратким ответом — частей в компьютерной форме экзамена нет, развёрнутых ответов и экспертной проверки тоже нет. Максимальный первичный балл за всю работу — 29, на работу отводится 235 минут. Задание 20 занимает в этой конструкции особое место:

оно входит в раздел «Теоретические основы информатики» — самый большой раздел кодификатора, 11 заданий и 11 первичных баллов;
вместе с заданием 19 и заданием 21 образует единственный на всём экзамене блок с общим условием: одна игра, три разных вопроса, три независимых балла;
задание 19 — базовый уровень и одно конкретное значение S; задание 20 (эта статья) — повышенный уровень и два значения S с условием «не за один ход, но за два»; задание 21 — высокий уровень и одно минимальное значение S, но уже для выигрышной стратегии Вани, второго игрока;
приём «В1 / П1 / В2» и рекурсия с мемоизацией, отработанные на задании 20, — это тот же аппарат, который нужен и для задания 21: там придётся строить классы В3, В4 и так далее вглубь дерева игры.

Задание 19 — одно значение S Задание 21 — вся стратегия целиком Все задания ЕГЭ по информатике Пробный экзамен ЕГЭ по информатике

План подготовки на 2 недели

Неделя 1 — ставим понятия и решатель

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

Неделя 2 — варианты условий и скорость

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

Проверьте себя на реальных заданиях

На Repet.ai собраны задания ЕГЭ по информатике из открытого банка ФИПИ. Решайте онлайн, проверяйте ответ мгновенно и разбирайте решение — бесплатно.

Перейти к практике

Частые вопросы

Часто задаваемые вопросы

Умение анализировать алгоритм логической игры двух игроков и находить значения параметра S, при которых у первого игрока (Пети) есть выигрышная стратегия строго определённого вида: он не может выиграть за один ход, но может гарантированно выиграть своим вторым ходом независимо от того, как ответит соперник (Ваня). В кодификаторе это КЭС 2.15 «Анализ алгоритма логической игры», требование 2.1, раздел «Теоретические основы информатики».

1 первичный балл по принципу «всё или ничего»: ответ либо полностью совпадает с эталоном, либо задание оценивается в 0 баллов. Частичного зачёта у задания 20 нет — он предусмотрен только для заданий 26 и 27. По обобщённому плану ФИПИ на задание 20 отводится примерно 8 минут. Уровень сложности — повышенный.

Задания 19, 20 и 21 — единственный на всём КЕГЭ блок с общим стимулом. Условие игры полностью описывается один раз в задании 19, а задания 20 и 21 к нему только отсылают («Для игры, описанной в задании 19…»). При этом все три задания проверяют разные умения и оцениваются независимо, по 1 баллу каждое (кроме 21, который тоже даёт 1 балл, но уровня «высокий»).

Ответ — это два числа в двух ячейках таблицы бланка, записанные в порядке возрастания: сначала меньшее значение S, потом большее. Формулировка ФИПИ прямо требует: «найденные значения запишите в ответе в порядке возрастания». Если числа перепутаны местами или найдено только одно значение, ставится 0 баллов, а не частичный балл.

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

На маленьких порогах — да, можно построить дерево игры руками, как показано в статье на тренировочном примере с порогом 8. Но в реальных заданиях банка пороги измеряются десятками и сотнями, диапазон S — десятками и сотнями значений, и переборный анализ руками за отведённые 8 минут практически невозможен. На КЕГЭ доступна среда программирования именно для таких задач.

Функция can_win_in_at_most вызывает сама себя рекурсивно для позиций, которые могут повторно встречаться при переборе разных ветвей игры и разных значений S. Без мемоизации одни и те же позиции пересчитывались бы много раз, а с lru_cache каждая пара (позиция, k) вычисляется ровно один раз и берётся из кеша при повторном обращении — это ускоряет перебор на порядки.

У всех трёх заданий общее условие игры и общий раздел кодификатора (КЭС 2.15), но разные вопросы. Задание 19 (базовый уровень) просит найти одно конкретное значение S при заданном сценарии первых ходов. Задание 20 (повышенный уровень, эта статья) просит найти два значения S с условием «не за один ход, но за два». Задание 21 (высокий уровень) переворачивает роль: нужно найти одно минимальное значение S, при котором выигрышная стратегия появляется уже у Вани, второго игрока.

Готовы взять балл повышенного уровня?

Задание 20 решается по чёткому алгоритму: разбираем формулировку на три условия, строим позиции В1, П1, В2, пишем решатель с мемоизацией — и перебор чисел перестаёт быть источником ошибок. Отработайте приём на реальных заданиях из открытого банка ФИПИ с мгновенной проверкой ответа.

Тренировать задание 20 Задание 19 — условие игры Все задания ЕГЭ по информатике