Каталог: Задания №19–21. Игра с камнями: код Кабанова

Банк задач: 180 Формат ЕГЭ 2026 Повышенный (3 балла за три вопроса) 8-12 мин Шаблоны решений на Python

Выберите номер задания ЕГЭ:

№1 №2 №3 №4 №5 №6 №7 №8 №9 №10 №11 №12 №13 №14 №15 №16 №17 №18 №19 №20 №21 №22 №23 №24 №25 №26 №27

Спецификация и суть задания №19

Тема кодификатора Выигрышные стратегии Пети и Вани: одна куча и две кучи

Сложность и баллы Повышенный (3 балла за три вопроса)

Рекомендуемое время 8-12 мин

Инструменты решения Python, lru_cache, any / all

Одна игра и три вопроса про начальное количество камней S. Мы пишем короткую функцию, которая умеет проверять «кто выигрывает за m ходов», и тремя вызовами отвечаем на все три вопроса.

Основные прототипы и разновидности

Тип 1: Одна куча

Состояние это одно число. Ходы: добавить камни, убрать, умножить или разделить.

Тип 2: Две кучи

Состояние это пара (a, b). Ход меняет одну из куч, игра кончается по сумме камней.

Тип 3: Особые правила

Например, удвоение запрещено, когда кучи равны. Такое условие попадает в функцию moves.

Теоретический фундамент и алгоритмы

Что от тебя хотят

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

Три вопроса и что вызвать

Как звучит вопрос	Что проверить в коде
№19. Петя не может выиграть первым ходом, но при любом его ходе Ваня выигрывает своим первым ходом	`f(S, 2)`
№19, вариант «возможно». Ваня выиграл первым ходом после неудачного хода Пети: при каком S это возможно	`any(f(x, 1) for x in moves(S))`
№20. У Пети есть стратегия: за один ход он не выигрывает, но выигрывает вторым ходом при любой игре Вани	`f(S, 3) and not f(S, 1)`
№21. Ваня выигрывает первым или вторым ходом при любой игре Пети, но не может гарантированно выиграть первым	`f(S, 4) and not f(S, 2)`

Идея Кабанова: считаем ходы по одному

Функция f(h, m) отвечает на вопрос «чем кончится игра, если сделать не больше m ходов». Вызываем её всегда для начального положения, когда ходит Петя. Тогда:

если m нечётное, ответ True означает «выигрывает Петя»;
если m чётное, ответ True означает «выигрывает Ваня».

Внутри функции три строки: «если игра кончилась, засчитываем победу тому, кто сделал последний ход»; «если ходы закончились, никто не выиграл»; «иначе пробуем все ходы». Для нашего игрока достаточно одного хорошего хода (any), а противника придётся проверить на любой ход (all).

Менять в коде нужно только две вещи: функцию moves (какие ходы бывают) и условие конца игры. Весь остальной код переписывать не придётся ни в одной задаче.

Разбор 1: одна куча

Куча из S камней, S ≥ 3215. За ход можно убрать 4 камня, убрать 5 камней или уменьшить число камней в 3 раза (с округлением вверх). Игра заканчивается, когда в куче не более 3214 камней. Вопрос 1: сумма всех S, при которых выполнено условие №19. Вопрос 2: наименьшее и наибольшее S из №20. Вопрос 3: сколько значений S подходит под №21.

В левом окне округление вверх записано как (h + 2) // 3. Ответы: 38578, 9647 и 28938, 8. Они совпадают с ответами из банка.

Разбор 2: две кучи

Две кучи: в первой 6 камней, во второй S (от 1 до 93). За ход можно добавить в любую кучу один камень или увеличить любую кучу в четыре раза. Игра заканчивается, когда в двух кучах вместе не меньше 100 камней. Три вопроса те же.

Состояние теперь пара (a, b), ходы возвращают пары, конец игры по sum(h). Правое окно даёт ответы 4, 3 и 23, 22. Первый вопрос здесь в варианте «возможно», поэтому в нём стоит any по первому ходу Пети.

Округление вверх в целых числах. Деление с округлением вверх пишут (h + 2) // 3 для деления на 3 и (h + k - 1) // k для любого k. Обычное // округляет вниз и даёт другой ответ.

Лайфхаки и фишки для ускорения

Совет

Для двух куч состояние хранится кортежем (a, b): списки нельзя класть в lru_cache, кортежи можно.

Совет

Диапазон S бери из условия: для одной кучи начни с порога плюс один, для двух возьми диапазон второй кучи.

Совет

Сначала проверь функцию на очень маленькой игре, где исход можно разобрать руками: например, куча до 5 камней и ходы +1 и ×2.

Частые ошибки и экзаменационные ловушки

❌ Путать, за кого True
При нечётном m в f True значит победу Пети, при чётном победу Вани.

✅ Перед вызовом проверь чётность m и держи в голове таблицу: №19 это m = 2, №20 m = 3, №21 m = 4.

❌ Забыть про not f(S, 1) во втором и третьем вопросах
В ответ попадут значения S, где Петя (или Ваня) выигрывает слишком рано.

✅ Условие «не может выиграть первым ходом» записывать явно: and not f(S, 1) и and not f(S, 2).

❌ Забыть ход, который запрещён или особый
Если при равных кучах удвоение запрещено, а в moves оно осталось, ответ окажется неверным.

✅ Правила игры целиком вписывать в moves: условие if a == b внутри функции.

💀 ГРОБ №19–21: Две кучи с особым правилом

Бывает, что одну из куч нельзя трогать при определённом условии, или что ход зависит от того, какая куча больше. Тогда набор ходов у разных позиций получается разный.

Алгоритм решения: Всё это решается внутри `moves(h)`: вытащи `a, b = h`, и допиши нужные `if` перед `return`. Остальной код остаётся без изменений.

Практические задачи из банка КИМ (Всего: 180)

Решать в песочнице СмартКИМ

Задача #8999 №19 ЕГЭ

Каталог: Задания №19–21. Игра с камнями: код Кабанова

Спецификация и суть задания №19

Основные прототипы и разновидности

Теоретический фундамент и алгоритмы

Что от тебя хотят

Три вопроса и что вызвать

Идея Кабанова: считаем ходы по одному

Разбор 1: одна куча

Разбор 2: две кучи

Лайфхаки и фишки для ускорения

Частые ошибки и экзаменационные ловушки

Практические задачи из банка КИМ (Всего: 180)

Готовьтесь к ЕГЭ эффективно со СмартКИМ