Базовый (1 балл) Время: 3-5 мин Python Словарь Динамика Все задачи №13 в каталоге

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

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

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

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

Исполнитель умеет, например, +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»), порядок обхода меняется: идём от большего числа к меньшему, и запрет на выход за границу ставим снизу.

Разновидности и прототипы задания на экзамене

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

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

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

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

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

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

Код решения на Python

Запустить код в онлайн-песочнице

{value: ways}dict.get()def count(start, end)[0] * (end + 1)for step in range(7)+=

Программы из ровно 7 команд

ways = {3: 1}

for step in range(7):
    new_ways = {}
    for value in ways:
        for result in (value + 1, value + 4, value * 2):
            if result not in new_ways:
                new_ways[result] = 0
            new_ways[result] += ways[value]
    ways = new_ways

print(ways.get(27, 0))

Задача из базы, которую решает этот код Открыть в песочнице

Любой длины: обязательное 15, запрещённое 7

def count(start, end):
    ways = [0] * (end + 1)
    ways[start] = 1
    for v in range(start, end):
        if v == 7:
            ways[v] = 0
        ways[v + 1] += ways[v]
        if v + 3 <= end:
            ways[v + 3] += ways[v]
        if v * 2 <= end:
            ways[v * 2] += ways[v]
    return ways[end]


print(count(2, 15) * count(15, 25))

Задача из базы, которую решает этот код Открыть в песочнице

Типичные ошибки

✕ Не так

Складывать этапы

Считать ответ как count(A, C) + count(C, B).

✓ Так

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

✕ Не так

Перебирать программы рекурсией без запоминания

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

✓ Так

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

✕ Не так

Забыть границу сверху

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

✓ Так

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

ГРОБ

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

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

Как обойти

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

Лайфхаки на экзамене

Хранишь способы в словаре ways, а не в списке? Тогда большие числа и пропуски не мешают.
Запрещённое число обнуляй до того, как передавать из него способы дальше. Иначе запрет не сработает.
Проверка: возьми маленькую задачу, где ответ можно посчитать пальцами (например, из 1 в 4 командами +1 и ×2), и сравни с программой.

Банк реальных задач №13 Открыть в тренажере СмартКИМ