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

Решение:

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

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

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

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

$k$ — команд В	$n$ — команд А	Количество программ $C_{n+k}^{\,k}$
0	32	$C_{32}^{0} = 1$
1	27	$C_{28}^{1} = 28$
2	22	$C_{24}^{2} = 276$
3	17	$C_{20}^{3} = 1140$
4	12	$C_{16}^{4} = 1820$
5	7	$C_{12}^{5} = 792$
6	2	$C_{8}^{6} = 28$

Складываем: $1 + 28 + 276 + 1140 + 1820 + 792 + 28 = 4085$.

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

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(7, 71))

Ответ: 4085