21 задание ЕГЭ информатика: разбор игры с двумя кучами
21 задание ЕГЭ по информатике — это теория игр: нужно найти значение S, при котором Ваня выигрывает за один или два своих хода, но не выигрывает первым ходом. Решается тремя способами: вручную по дереву партий, в Excel или программой на Python. Ниже порядок действий, шаблон кода и типичные ошибки.
Что требуется в задании 21
Как правило, в условии две кучи камней (в одной известное число, в другой S) или одна куча. Ходы заданы правилом: добавить камень, увеличить количество в несколько раз и так далее. Игра заканчивается, когда общее число камней достигает порога, а победил тот, кто сделал последний ход.
Типичный вопрос 21 задания: найти наименьшее или такое S, при котором выполнены два условия сразу. Первое: у Вани есть выигрышная стратегия, позволяющая выиграть первым или вторым ходом при любой игре Пети. Второе: у Вани нет стратегии, которая выигрывает первым ходом. Точную формулировку всегда сверяй с текстом варианта: в нём бывают отличия, например, просят наименьшее, наибольшее или количество значений.
Ответ — одно целое число, поэтому ошибка в одном ходе дерева сразу даёт неверный результат. Это и делает задание высокого уровня сложности.
19 20 21 задание ЕГЭ информатика: чем они отличаются
Задания 19, 20 и 21 — одна серия про одну и ту же игру, только вопросы нарастают по сложности. Поэтому их удобно разбирать вместе и использовать один и тот же код.
Если ты уверенно решаешь 19 и 20, то 21 — это те же правила плюс более длинная цепочка ходов.
- Задание 19: Петя не выигрывает первым ходом, но может выиграть вторым при любой игре Вани.
- Задание 20: Ваня выигрывает первым ходом после любого хода Пети, при этом у Пети нет выигрыша первым ходом. Обычно ищут два значения S.
- Задание 21: Ваня выигрывает не позднее своего второго хода при любой игре Пети, но не может выиграть первым ходом.
- Разбор каждого номера со своими примерами есть на страницах /zadaniya/informatics/19/, /zadaniya/informatics/20/ и /zadaniya/informatics/21/.
Пример задания из банка «Ранга»
На этом примере хорошо видно, как условие про первый ход Вани превращается в проверку позиций после каждого хода Пети. Реши его сам с таблицей или кодом и сверь результат с проверенным ответом, чтобы убедиться, что твой подход работает.
Условие. Два игрока, Петя и Ваня, играют в следующую игру. Перед ними две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч один камень или увеличить количество камней в одной из куч в два раза.
Игра завершается, когда суммарное количество камней становится не менее 53; победителем считается игрок, сделавший последний ход.
В первой куче 7 камней, во второй куче S камней. Найди наименьшее значение S, при котором Ваня выигрывает своим первым ходом при любой игре Пети. В ответе запиши только целое число.
Показать ответ и решение
- Выигрыш второго игрока: из начальной позиции первый игрок выиграть не может, и после КАЖДОГО его хода получается позиция, выигрышная одним ходом.
- Построй дерево игры на два уровня: четыре хода первого игрока, из каждого — четыре ответа.
Ответ: 0
Как строить дерево игры и позиции
Дерево партий — это схема: из каждой позиции выходят стрелки на все позиции, достижимые одним ходом. Позиция — это пара чисел (количество в первой куче, количество во второй) и тот, чей сейчас ход.
Сначала определи конечные позиции: сумма уже достигла порога, значит, игрок, который шёл перед этим, победил. Затем двигайся от конца к началу и каждой позиции присваивай статус.
- Выигрышная в один ход: существует ход, после которого сумма достигает порога.
- Проигрышная: любой ход ведёт в позицию, из которой соперник выигрывает сразу.
- Выигрышная во второй ход: есть ход, после которого все ответы соперника ведут в позиции, где выигрывает ты.
- Если ходов у соперника несколько, проверяй все ответы, а не один удобный.
21 задание ЕГЭ информатика руками: порядок решения
Вручную задание решается, когда числа небольшие или есть закономерность. Работай от порога вниз: сначала найди все значения S, при которых Петя выигрывает первым ходом. Эти S Ване не подходят: нужно, чтобы он выигрывал, а не Петя.
Дальше для каждого оставшегося S разбери каждый возможный ход Пети: после него должна возникнуть позиция, из которой Ваня выигрывает первым или вторым ходом. Достаточно найти одно подходящее действие Вани на каждый ход Пети. Затем проверь второе условие: Ваня не выигрывает первым ходом в начале, то есть нет позиции, где один ход сразу доводит сумму до порога.
Для ускорения запиши таблицу: строка — значение S, столбцы — ходы Пети и ответ Вани. Просматривай значения S по возрастанию и остановись на первом, где выполняются оба условия, если нужно наименьшее.
21 задание ЕГЭ информатика Python: шаблон кода
Программа на Python избавляет от ручного перебора и ошибок в арифметике. Идея одна: функция принимает позицию и возвращает, кто выигрывает и за сколько ходов, а перебор значений S идёт циклом.
Шаблон строится так: описываешь функцию всех возможных ходов, затем функцию-проверку. В ней: если сумма достигла порога, то прошлый игрок выиграл; иначе смотришь результаты всех позиций после хода и сравниваешь. Для 19–21 заданий хватает рекурсии с ограничением глубины в нужное число ходов.
Для 21 задания пригодятся три функции: выигрыш в один ход, выигрыш не позднее второго хода при любой игре соперника, и итоговое условие, которое объединяет их. Внутри используй any для «существует ход» и all для «при любой игре соперника». Путаница между any и all — самая частая причина неверного ответа.
Перед отправкой ответа запусти код на примере из демоверсии, где ответ известен, и сравни. Демонстрационные варианты доступны на сайте ФИПИ (fipi.ru).
19 21 задание ЕГЭ информатика Excel: когда подходит таблица
Excel выручает, если игра с одной кучей или если ходы позиции можно записать формулой. Тогда в строке ты расписываешь позиции по возрастанию, а в соседних столбцах считаешь статус: выигрыш первым ходом, проигрыш, выигрыш вторым ходом.
Для двух куч таблица становится двумерной, и формулы получаются громоздкими. В этом случае Python удобнее. Выбирай тот инструмент, которым владеешь лучше, и тренируйся именно в нём: на экзамене времени на смену подхода не будет.
Если в таблице получается много ссылок на соседние строки, проверь выборочно два-три значения вручную: это быстрый способ найти ошибку в формуле.
Типичные ошибки и как проверить себя
Основные ошибки в 21 задании повторяются из года в год. Проверь по списку перед тем, как записать ответ.
- Перепутаны условия: в 19 выигрывает Петя, в 20 и 21 — Ваня.
- Не исключено значение S, при котором Петя выигрывает первым ходом.
- Не учтён один из ходов (например, удвоение кучи) в переборе.
- Проверен только один ответ соперника вместо всех.
- Не проверено условие «не выигрывает первым ходом».
- Неверная граница порога: «не менее» означает включительно.
- Ответ взят из оценки «примерно», а не из полного перебора значений S.
Частые вопросы
Что нужно знать, чтобы решить 21 задание по информатике?
Нужно понимать, что такое выигрышная и проигрышная позиции, и уметь строить дерево партий. Также пригодятся рекурсия и базовые циклы в Python либо таблица в Excel. Если с основами сложно, начни с материалов по информатике с нуля: /blog/podgotovka-ege-informatika-s-nulya/.
Можно ли решить 19, 20 и 21 задания одним кодом?
Да, функция выигрыша за заданное число ходов подходит для всех трёх номеров. Меняется только итоговое условие: кто выигрывает, за сколько ходов и что запрещено в первом ходу. Сохрани шаблон и меняй только последнюю проверку.
Что лучше: решать руками, в Excel или на Python?
Зависит от числа камней и количества куч. Для небольших значений вручную быстро, для одной кучи удобен Excel, для двух куч и сложных ходов надёжнее Python. Лучше освоить один способ до уверенного результата и использовать второй для проверки.
Где взять задачи для тренировки?
Открытые демоверсии и спецификации публикует ФИПИ на fipi.ru, а условия формата проверяй на официальных материалах. Для практики с проверкой ответа можно пройти бесплатный тест: /free-test/.
Как понять, что ответ верный?
Проверь найденное S вручную: перебери все ходы Пети и убедись, что у Вани есть ответ. Затем проверь, что при этом S Ваня не выигрывает первым ходом, а для меньших значений условия не выполняются.
Полезно по теме
Читать дальше
Проверить себя в тренажёре
Открывается тренировочное задание в формате ЕГЭ: условие видно сразу, краткий ответ проверяется без регистрации.
Решить задание в тренажёреМатериал — разъяснение «Ранг». Официальные правила экзамена, расписание, шкалы баллов и перечни заданий публикуют ФИПИ (fipi.ru) и Рособрнадзор (obrnadzor.gov.ru). Мы не обещаем конкретных баллов: результат зависит от твоей работы.