Задание 19 ЕГЭ по информатике: анализ алгоритма логической игры

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

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

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

Проверяемые умения (КЭС 2.15, требование 2.1):

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

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

Параметр	Значение
Максимальный балл	1 первичный (полубаллов нет: ответ либо совпал с эталоном, либо 0)
Уровень сложности	Базовый (Б) — одно из 11 заданий базового уровня во всей работе
КЭС / код требования	2.15 «Анализ алгоритмов победы в игре по заданным правилам» / 2.1
Форма ответа	Краткий ответ: одно целое число
Файл	Не прилагается
Специализированное ПО	Не требуется
Рекомендуемое время	6 минут (примерное время выполнения задания по обобщённому плану ФИПИ)
Связанные задания	Задание 20 (повышенный уровень, тот же КЭС 2.15, та же игра) и задание 21 (высокий уровень, та же игра, дерево игры)

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

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

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

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

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

«Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может: – добавить в кучу один камень – увеличить количество камней в куче в два раза. […] Игра завершается в тот момент, когда количество камней в куче становится не менее 29. […] Укажите такое значение S, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом.»
«Перед игроками лежат две кучи камней. […] За один ход игрок может добавить в одну из куч (по своему выбору) один камень или увеличить количество камней в куче в два раза. […] Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 59. […] Известно, что Ваня выиграл своим первым ходом после неудачного первого хода Пети. Укажите минимальное значение S, при котором такая ситуация возможна.»
«Игра завершается в тот момент, когда произведение количеств камней в кучах становится не менее 144. […] Известно, что Ваня выиграл своим первым ходом после неудачного первого хода Пети. Укажите минимальное значение S, когда такая ситуация возможна.»

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

Как записывается ответ. Ответ на задание 19 — одно целое число, минимальное значение параметра S. Ответы на задания КЕГЭ вводятся с клавиатуры прямо в компьютерную форму, в той форме, которая указана в инструкции к заданию: только число, без слова «камней», без пояснений и без единиц измерения.

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

Словарь темы: как говорить об игре

Позиция — полное описание текущего состояния игры: сколько камней в каждой куче. Одна куча — позиция это число; две кучи — пара чисел $(x, y)$ .
Ход — разрешённое правилами игры действие, переводящее одну позицию в другую: добавить камень или увеличить кучу в несколько раз.
Выигрышная позиция — позиция, из которой игрок, делающий ход, может действовать так, чтобы выиграть, как бы ни играл соперник.
Проигрышная позиция — позиция, из которой любой ход игрока ведёт в выигрышную позицию для соперника: что бы вы ни сделали, соперник побеждает.
Выигрыш за один ход — из позиции есть ход, который сразу завершает игру (сумма, размер кучи или произведение достигает порога).
Выигрышная стратегия за k ходов — план, который гарантирует игроку победу не позднее, чем через $k$ его собственных ходов, при любых ответных ходах соперника.

Задание 19 работает только с двумя первыми «этажами» этой классификации — выигрыш за 1 ход и выигрышная стратегия за 2 хода. Задания 20 и 21 идут дальше: 3, 4 и более ходов, а также полное дерево игры.

Разметка позиций с конца: В1, П1, В2, П2…

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

В1 — выигрыш первым ходом

Позиция называется В1, если из неё существует ход, который сразу завершает игру. Игрок, оказавшийся в такой позиции, побеждает одним действием.

П1 — любой ход ведёт в В1

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

В2, П2 и дальше

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

Мини-пример: одна куча, порог 10

Пусть куча растёт только удвоением, игра заканчивается при размере кучи не менее 10. Тогда:

куча = 5:  ×2 → 10, это конец игры              → В1
куча = 6:  ×2 → 12, это конец игры              → В1
куча = 3:  ×2 → 6;  позиция "6" это В1,
           а других ходов нет                    → П1
куча = 4:  ×2 → 8;  позиция "8" это В1
           (8×2=16 ≥ 10), других ходов нет        → П1
куча = 2:  ×2 → 4;  позиция "4" это П1            → В2

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

Почему S ищут снизу вверх и берут минимальное

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

Отсюда простой и надёжный способ решения: перебирать S по возрастанию, начиная с $S=1$ , и для каждого значения проверять условие функцией $\text{wins}$ из следующего блока. Первое же подошедшее значение — это и есть ответ, потому что перебор идёт снизу вверх, а задание прямо просит минимальное S. Проверять весь диапазон до конца не нужно: как только найдено первое совпадение, цикл можно прервать.

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

Универсальный решатель на Python — один код для 19, 20 и 21

Разметка «с конца» из предыдущего блока прямо переписывается в рекурсию с мемоизацией. Функция $\text{label}$ принимает позицию, функцию $\text{moves}$ (какие ходы доступны из позиции) и функцию $\text{is\_over}$ (закончилась ли игра в этой позиции), и возвращает пару «сколько ходов нужно» и «В или П»:

from functools import lru_cache

def label(pos, moves, is_over):
    @lru_cache(maxsize=None)
    def rec(p):
        children = moves(p)
        if any(is_over(q) for q in children):
            return (1, "B")
        rest = [rec(q) for q in children if not is_over(q)]
        p_levels = [k for k, t in rest if t == "P"]
        if p_levels:
            return (min(p_levels) + 1, "B")
        b_levels = [k for k, t in rest if t == "B"]
        return (max(b_levels), "P")
    return rec(pos)

def wins(pos, moves, is_over):
    return label(pos, moves, is_over)[1] == "B"

Функция $\text{wins}$ отвечает на вопрос «выиграет ли игрок, который сейчас должен ходить, при оптимальной игре с обеих сторон» — это ядро задач 20 и 21. Для задания 19 вопрос точнее: нужен не общий выигрыш, а выигрыш ровно за 1 ход, то есть метка $(1, \text{«B»})$ . Ниже — обёртка под оба варианта формулировки задания 19 (двумя кучами и суммой, и одной кучей с «любым ходом»):

def moves_two_piles(p):
    x, y = p
    return [(x + 1, y), (2 * x, y), (x, y + 1), (x, 2 * y)]

def solve_after_bad_move(A, N, S_max):
    is_over = lambda p: p[0] + p[1] >= N
    for S in range(1, S_max + 1):
        start = (A, S)
        if is_over(start):
            continue
        if label(start, moves_two_piles, is_over) == (1, "B"):
            continue                       # Петя сам выигрывает за 1 ход
        kids = [q for q in moves_two_piles(start) if not is_over(q)]
        if any(label(q, moves_two_piles, is_over) == (1, "B") for q in kids):
            return S                       # нашли неудачный ход Пети
    return None

def moves_one_pile(s):
    return [s + 1, 2 * s]

def solve_any_move_loses(N, S_max):
    is_over = lambda s: s >= N
    for S in range(1, S_max + 1):
        if is_over(S):
            continue
        if label(S, moves_one_pile, is_over) == (1, "P"):
            return S                       # П1: любой ход ведёт в В1
    return None

print(solve_after_bad_move(5, 59, 53))     # 14
print(solve_any_move_loses(29, 28))        # 14

Это ровно две формы одного и того же вопроса. «При любом ходе Пети Ваня выигрывает первым ходом» — это прямая проверка $\text{label(старт)} = (1, \text{«П»})$ . «Ваня выиграл первым ходом после неудачного хода Пети» — это более мягкое условие: сам Петя не в В1, но хотя бы один его ход ведёт в позицию В1 (не обязательно все). Обе формы дают один и тот же класс задач, просто с разной строгостью формулировки.

Для заданий 20 и 21 меняются только $\text{moves}$ и $\text{is\_over}$ (если условие другое) и запрос к $\text{label}$ : задание 20 обычно просит диапазон S, при которых стартовая позиция — строго В2 (выигрыш ровно за 2 хода), а задание 21 требует построить дерево игры и посчитать число листьев или ходов — это делается обходом той же функции $\text{moves}$ с построением дерева вместо простой метки. Подробный разбор — в статьях про задание 20 и про задание 21.

Главная ловушка: «не менее» и кто ходит первым

Условие завершения игры в задании 19 всегда сформулировано как «не менее» порога (нестрогое неравенство): «камней становится не менее 29», «суммарное количество камней становится не менее 59». Это значит: достаточно попасть ровно на порог, чтобы выиграть, а не только превысить его. В коде это ${\ge}\ N$ , а не ${>}\ N$ . Перепутанный знак сдвигает каждую границу на единицу и портит весь ответ.

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

Третья ловушка — не путать «выиграть» и «сделать ход». Игра заканчивается сразу, как только позиция достигает порога, — дальше ходов не будет. Поэтому при проверке хода нужно сразу проверять условие окончания на позиции после хода, а не после хода соперника.

Три вида условия окончания игры

В открытом банке ФИПИ задание 19 встречается в трёх вариантах — они отличаются тем, как считается общий «счёт» игры и сколько куч камней на столе:

Вариант	Куч	Условие окончания	Ходы
Одна куча	1	размер кучи ${\ge}\ N$	+1 камень или ×2
Две кучи, сумма	2	$x + y \ge N$	+1 в любую кучу или ×2 любой кучи
Две кучи, произведение	2	$x \cdot y \ge N$	+1 в любую кучу или ×2 любой кучи

Механика ходов во всех трёх вариантах одна и та же — меняется только функция $\text{is\_over}$ в коде решателя. Первое, что нужно сделать, взяв задание 19, — определить, какой из трёх вариантов перед вами: от этого зависит, что именно проверяет условие «не менее N».

Алгоритм решения задания 19

Определите вариант условия. Одна куча или две; порог считается по сумме, по размеру одной кучи или по произведению. Выпишите доступные ходы и число N.
Выпишите начальную позицию. Она зависит от параметра S — второй (или единственной) кучи. Диапазон S всегда дан в условии, но для задания 19 он не важен: перебор всё равно начинается с 1.
Определите, что именно спрашивает вопрос. «При любом ходе Пети Ваня выигрывает первым ходом» — это позиция П1 у Пети. «Ваня выиграл первым ходом после неудачного хода Пети» — это позиция, из которой Петя не выигрывает за 1 ход, но хотя бы один его ход ведёт в В1.
Переберите S от 1 и выше, для каждого S соберите позицию и проверьте условие из шага 3 функцией $\text{label}$ . Как только условие выполнилось — это и есть минимальное S, дальше можно не считать.
Проверьте себя вручную на найденном S: сам игрок, ходящий первым, не должен уметь завершить игру одним ходом, а лучший возможный ход соперника после любого хода первого игрока обязан завершать игру.
Запишите одно число — найденное минимальное S. Дополнительных пояснений форма ответа не предусматривает.

Доведите разбор позиций до автоматизма

Прорешайте 10–15 игр подряд — и разметка «с конца» начнёт занимать пару минут. Задания 19 ЕГЭ по информатике из банка ФИПИ с проверкой ответа — на Repet.ai.

Открыть тренажёр

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

Пример 1. Одна куча, «при любом ходе Пети»

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

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

Решение:

Одна куча, порог $N = 29$ , ходы «+1» и «×2». Из кучи в $S$ камней ход «+1» даёт $S+1$ , ход «×2» даёт $2S$ . Так как $2S \ge S+1$ при любом $S \ge 1$ , самый сильный ход — удвоение. Значит выиграть за один ход можно ровно тогда, когда $2S \ge 29$ , то есть при $S \ge 15$ .

Условие «Петя не может выиграть за один ход» — это $S \le 14$ .

Дальше нужно, чтобы любой ход Пети приводил к куче, из которой Ваня выигрывает одним ходом, то есть к куче не менее чем в 15 камней:

ход "+1": S+1 ≥ 15  →  S ≥ 14
ход "×2": 2S  ≥ 15  →  S ≥ 8 (точнее S ≥ 7,5, S ≥ 8)

Вместе с $S \le 14$ остаётся единственное значение: S = 14.

Проверка: из кучи в 14 камней Петя получает 15 или 28 камней — обе меньше 29. Из 15 камней Ваня удваивает и получает 30. Из 28 камней Ваня добавляет камень и получает 29. Оба случая — не меньше 29, значит Ваня выигрывает первым ходом при любом ходе Пети. Ответ подтверждён и перебором на Python: 14.

Пример 2. Две кучи, сумма, «неудачный ход Пети»

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

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

Решение:

Позицию обозначим $(x, y)$ , порог $N = 59$ . За один ход сумма растёт либо на 1 (добавили камень), либо на $x$ , либо на $y$ (удвоили соответствующую кучу). Значит одним ходом можно прибавить не больше $\max(x, y, 1)$ .

Нужен неудачный ход Пети, после которого Ваня заканчивает игру: из позиции $(5, S)$ за два хода подряд должно набраться не менее 59 камней. Больше всего даёт двукратное удвоение большей кучи: $(5, S) \to (5, 2S) \to (5, 4S)$ , всего $5 + 4S$ камней — это больше, чем даёт любая другая пара ходов.

Условие $5 + 4S \ge 59$ равносильно $S \ge 13{,}5$ , то есть минимальное целое — S = 14.

Проверка: сам Петя выиграть не может — удвоив бóльшую кучу, он получит $5 + 2 \cdot 14 = 33 < 59$ . Но если он удвоит вторую кучу, получится позиция $(5, 28)$ ; тогда Ваня удваивает её ещё раз и получает $(5, 56)$ , сумма 61 — не меньше 59, Ваня выигрывает первым ходом. Ответ подтверждён перебором на Python: 14.

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

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

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

Решение:

Здесь порог считается по произведению $p = xy$ , а не по сумме — это меняет всю арифметику, но не метод. Добавление камня даёт $(a+1)b = p + b$ или $a(b+1) = p + a$ , а удвоение любой кучи даёт ровно $2p$ . Поскольку $a \le p$ и $b \le p$ , удвоение — самый сильный ход, и выиграть за один ход можно ровно тогда, когда $2p \ge 144$ , то есть $p \ge 72$ .

Из старта $(2, S)$ ходы Пети дают произведения $3S$ , $4S$ (двумя способами) и $2S+2$ . Наибольшее из них — $4S$ , поэтому порог 72 раньше всего достигает именно оно: $4S \ge 72 \Leftrightarrow S \ge 18$ .

При $S < 18$ максимум, что доступно после хода Пети, — $4 \cdot 17 = 68 < 72$ , и Ваня физически не может закончить игру своим ходом. Значит минимальное подходящее значение — S = 18.

Проверка при S = 18: стартовое произведение $2 \cdot 18 = 36$ , игра продолжается; Петя удваивает вторую кучу — $(2, 36)$ , произведение 72, это меньше 144, ход не завершил игру; Ваня удваивает любую кучу и получает произведение 144 — игра закончена, победил Ваня. Ответ подтверждён перебором на Python: 18.

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

Перепутали «не менее» с «более»

Порог в задании 19 всегда нестрогий: ${\ge}\ N$ , а не ${>}\ N$ . Позиция ровно на пороге уже завершает игру. Ошибка на единицу здесь сдвигает весь ответ.

Проверили не тот ход как «самый сильный»

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

Спутали «любой ход» и «хотя бы один ход»

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

Забыли, что Петя ходит первым

Позиция после старта — это всегда позиция, из которой ходит Петя. Если посчитать так, будто первый ход делает Ваня, получится позиция на один слой глубже и неверный ответ.

Взяли диапазон S из условия как готовый ответ

Диапазон $1 \le S \le \dots$ в условии — это только ограничение на входные данные, а не подсказка к ответу. Минимальное S ищется перебором и почти никогда не совпадает с границами диапазона.

Забыли проверить, что сам первый игрок не выигрывает за 1 ход

Условие «Петя не может выиграть за один ход» — обязательная часть задачи, а не формальность. Без неё можно найти S, при котором Петя выигрывает сам, а условие задачи требует прямо противоположного.

Перепутали задание 19 с заданиями 20 и 21

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

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

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

Задание 19 (базовый уровень) — найти минимальное S, при котором второй игрок выигрывает своим первым ходом. Это разметка В1/П1.
Задание 20 (повышенный уровень) — найти диапазон значений S, при которых у одного из игроков есть выигрышная стратегия за фиксированное число ходов. Это разметка на несколько шагов глубже (В2, П2 и далее).
Задание 21 (высокий уровень) — построить дерево игры и посчитать числовую характеристику стратегии игрока (например, количество способов выиграть или минимальное число ходов до обязательного выигрыша).

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

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

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

Неделя 1 — язык игры и разметка позиций

День 1–2: выучите словарь темы (позиция, ход, выигрышная и проигрышная позиция) и разберите разметку В1/П1 на маленьком примере — куче из 5–10 камней с порогом 10–15, вручную, без кода. День 3–4: разберите все три вида условия окончания игры — по сумме, по размеру одной кучи и по произведению — и научитесь быстро определять, какой самый сильный ход в каждом виде. День 5–7: решите 8–10 заданий 19 из открытого банка ФИПИ вручную, каждый раз явно выписывая, какая позиция В1, а какая — П1.

Неделя 2 — код и скорость

День 1–3: наберите и запустите универсальный решатель из этой статьи, проверьте его на всех трёх примерах. Замените $\text{moves}$ и $\text{is\_over}$ для своего варианта условия — потренируйтесь делать это быстро, не переписывая остальной код. День 4–5: решайте задания на время — 6 минут на задание, включая чтение условия и запись ответа. День 6–7: прорешайте подряд задания 19, 20 и 21 по одному и тому же условию игры, чтобы почувствовать, как один и тот же решатель работает на всех трёх уровнях сложности. Проверьте себя в тренажёре на заданиях из банка ФИПИ.

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

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

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

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

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

Умение анализировать простую игру двух игроков с полной информацией: кучи камней, ходы по очереди, условие завершения игры. В кодификаторе это элемент содержания 2.15 «Анализ алгоритмов победы в игре по заданным правилам», проверяемое требование 2.1. Обычно нужно найти минимальное значение параметра S, при котором второй игрок гарантированно выигрывает своим первым ходом.

1 первичный балл по принципу «всё или ничего» — ответ либо полностью совпадает с эталоном, либо задание оценивается в 0. По обобщённому плану ФИПИ на задание 19 отводится примерно 6 минут. Уровень сложности — базовый.

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

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

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

Нужно сравнить, на сколько каждый допустимый ход увеличивает контролируемую величину (сумму, размер кучи или произведение). Для сумм и произведений самый сильный ход почти всегда — удвоение бóльшей кучи, но это стоит явно проверить перебором всех вариантов хода, а не считать заранее известным.

Потому что порог нестрогий: игра заканчивается, как только количество камней (или сумма, или произведение) достигает порога или превышает его. В коде это условие вида «≥ N», а не «> N». Перепутанный знак сдвигает границу на единицу и портит весь ответ.

Ответ — одно целое число, минимальное значение параметра S. КЕГЭ сдаётся за компьютером, ответы вводятся в компьютерную форму в том виде, который указан в инструкции к заданию: только число, без слов и единиц измерения.

Готовы закрыть весь игровой блок 19–21?

Задание 19 — самое короткое из трёх: один приём разметки, 6 минут, один балл. Освоив разметку В1/П1 и универсальный Python-решатель, вы получаете готовую базу для заданий 20 и 21. Отработайте задание 19 на реальных играх из открытого банка ФИПИ с мгновенной проверкой ответа.

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