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

Решение:

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

$$2 n + 7 k = 44.$$

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

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

$k$ — команд В	$n$ — команд А	Количество программ $C_{n+k}^{\,k}$
0	22	$C_{22}^{0} = 1$
2	15	$C_{17}^{2} = 136$
4	8	$C_{12}^{4} = 495$
6	1	$C_{7}^{6} = 7$

Складываем: $1 + 136 + 495 + 7 = 639$.

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

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

print(f(5, 49))

Ответ: 639