Задание №23 — Поиск количества программ

Решение:

Все команды только увеличивают число на экране, поэтому траектория строго возрастает и ни одно число не может встретиться в ней дважды.

Траектория обязана содержать число $6$, поэтому каждая подходящая программа однозначно распадается на две части: $1 \to 6$ и $6 \to 35$. По правилу умножения ответ равен произведению количеств программ для этих участков.

Пусть $f(x, y)$ — количество программ, переводящих $x$ в $y$: $f(x, x) = 1$ (пустая программа), $f(x, y) = 0$ при $x \gt y$ (число уже «перескочило» цель, а уменьшать команды не умеют). В остальных случаях перебираем первую команду («прибавить 2», «прибавить 3» или «умножить на 5»):

$$f(x, y) = f(x + 2,\, y) + f(x + 3,\, y) + f(5x,\, y).$$

Число $21$ траектория содержать не должна, поэтому переход в него запрещаем — соответствующее слагаемое отбрасываем.

from functools import lru_cache

@lru_cache(None)
def f(x, y):          # сколько программ переводят число x в число y
    if x == y:
        return 1
    if x > y:
        return 0      # перескочили - назад команд нет
    s = 0
    for z in (x + 2, x + 3, x * 5):
        if z != 21:
            s += f(z, y)
    return s

print(f(1, 6) * f(6, 35))

Получаем $f(1, 6) = 2$ и $f(6, 35) = 846$, то есть всего $2 \cdot 846 = 1692$ программ. Ответ: 1692