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

Решение:

Команда А увеличивает число на $2$, команда В — на $10$; порядок команд на итоговое число не влияет, важно лишь, сколько раз использована каждая. Всего надо прибавить $71 - 5 = 66$. Если команда А использована $n$ раз, а команда В — $k$ раз, то

$$2 n + 10 k = 66.$$

Отсюда подходят только $k = 0, 1, 2, 3, 4, 5, 6$ (при остальных $k$ остаток $66 - 10k$ не делится на $2$ нацело или отрицателен).

Программа — это последовательность команд, поэтому при фиксированных $n$ и $k$ количество программ равно числу способов расставить $k$ команд В среди всех $n + k$ команд, то есть $C_{n+k}^{\,k}$.

$k$ — команд В	$n$ — команд А	Количество программ $C_{n+k}^{\,k}$
0	33	$C_{33}^{0} = 1$
1	28	$C_{29}^{1} = 29$
2	23	$C_{25}^{2} = 300$
3	18	$C_{21}^{3} = 1330$
4	13	$C_{17}^{4} = 2380$
5	8	$C_{13}^{5} = 1287$
6	3	$C_{9}^{6} = 84$

Складываем: $1 + 29 + 300 + 1330 + 2380 + 1287 + 84 = 5411$.

Тот же результат даёт короткая программа:

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 + 10):
        s += f(z, y)
    return s

print(f(5, 71))

Ответ: 5411