Каталог: Задание №13. Калькулятор: считаем программы

Банк задач: 113 Формат ЕГЭ 2026 Базовый (1 балл) 3-5 мин Шаблоны решений на 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

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

Тема кодификатора Подсчёт количества программ исполнителя, динамика по значениям, обязательные и запрещённые числа

Сложность и баллы Базовый (1 балл)

Рекомендуемое время 3-5 мин

Инструменты решения Python, Словарь, Динамика

У Калькулятора есть несколько команд («прибавить 1», «умножить на 2»...). Сколько существует программ, которые из числа A делают число B, возможно, с условием на длину или на промежуточные числа? Решается подсчётом: сколько способов дойти до каждого числа.

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

Тип 1: Программы из ровно N команд

Длина программы задана. Идём по шагам и копим словарь «число: сколько способов».

Тип 2: Программа любой длины

Считаем массив ways по возрастанию чисел: в каждое число можно прийти разными командами.

Тип 3: Обязательное или запрещённое число

Путь режем на части: до обязательного числа и после. Запрещённое число обнуляем.

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

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

Исполнитель умеет, например, +1, +4, ×2. Программа это последовательность таких команд. Спрашивают, сколько различных программ превращает 3 в 27 (иногда с условием на длину). Две программы разные, если отличаются хотя бы одной командой.

Идея: считаем, сколькими способами можно прийти в число

Не перебирай программы по одной: их миллионы. Лучше посчитай для каждого числа, сколько способов дойти до него. Если в число v можно прийти из u1, u2 и u3, то способов дойти до v столько, сколько до u1, плюс до u2, плюс до u3.

Два вида условия

Длина задана («из 7 команд»). Идём шаг за шагом: после каждого шага запоминаем, в каких числах мы можем оказаться и сколькими способами. Ровно столько шагов, сколько сказано.
Длина любая. Заводим массив ways и проходим числа по возрастанию. Для каждого числа «раздаём» его способы тем числам, куда ведут команды.

Обязательные и запрещённые числа

Если траектория должна проходить через число C, считай отдельно путь из A в C и из C в B, а ответы перемножай. Если траектория не должна проходить через число D, просто обнуляй способы в D, как будто в этом числе стена.

Умножай, а не складывай. Каждый путь «до C» можно продолжить любым путём «после C». Поэтому ответ равен произведению, а не сумме.

Разбор 1: программы из 7 команд

Исполнитель Калькулятор имеет команды: 1) прибавить 1, 2) прибавить 4, 3) умножить на 2. Сколько существует программ из 7 команд, которые число 3 преобразуют в число 27?

Первое окно ведёт словарь ways: сначала в нём только число 3 с одним способом. На каждом из 7 шагов строится новый словарь, куда складываются результаты всех трёх команд. Число 27 получается 37 способами.

Разбор 2: любой длины, с обязательным и запрещённым числом

Команды: A) прибавить 1, B) прибавить 3, C) умножить на 2. Сколько существует программ, которые число 2 преобразуют в число 25, при этом траектория содержит число 15 и не содержит число 7?

Функция count(start, end) из второго окна считает программы из start в end и обнуляет число 7. Ответ равен count(2, 15) * count(15, 25) и составляет 2716. Это задача из досрочного ЕГЭ-2026.

Если команды уменьшают число (например, «вычесть 1», «разделить на 2»), порядок обхода меняется: идём от большего числа к меньшему, и запрет на выход за границу ставим снизу.

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

Совет

Хранишь способы в словаре ways, а не в списке? Тогда большие числа и пропуски не мешают.

Совет

Запрещённое число обнуляй до того, как передавать из него способы дальше. Иначе запрет не сработает.

Совет

Проверка: возьми маленькую задачу, где ответ можно посчитать пальцами (например, из 1 в 4 командами +1 и ×2), и сравни с программой.

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

❌ Складывать этапы
Считать ответ как count(A, C) + count(C, B).

✅ Перемножать: count(A, C) * count(C, B).

❌ Перебирать программы рекурсией без запоминания
Число программ растёт как степень: на длине 20 цикл не завершится.

✅ Хранить количество способов для каждого числа и идти шаг за шагом.

❌ Забыть границу сверху
Считать пути в числа, которые уже больше нужного: они всё равно не вернутся.

✅ Результат больше end не учитывать (if v + 3 <= end).

💀 ГРОБ №13: Ограничение на число применений команды

Например, команду «×2» можно применять не более двух раз. Простой подсчёт числа способов этого не учитывает.

Алгоритм решения: Храни в состоянии не только число, но и счётчик применений: ключом словаря станет пара `(значение, сколько раз применили ×2)`.

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

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

Задача #9195 №13 ЕГЭ

Каталог: Задание №13. Калькулятор: считаем программы

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

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

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

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

Идея: считаем, сколькими способами можно прийти в число

Два вида условия

Обязательные и запрещённые числа

Разбор 1: программы из 7 команд

Разбор 2: любой длины, с обязательным и запрещённым числом

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

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

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

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