23.08 Прочие прототипы

Ключевое замечание, необходимое для решения задачи — заметим, что нет смысла рассматривать числа большие так как из них даже четырежды применив вторую операцию не получить число . Далее достаточно написать — количество программ заканчивающихся в числе и при этом использующие ровно шагов второго типа. База динамики . Переход в динамике: . Конечно стоит аккуратно проверять, что .

Решение динамикой

dp = [[0] * 5 for _ in range(16 * 20 + 1)]
dp[10][0] = 1
for cnt in range(5):
    for x in range(16 * 20 + 1):
        if x + 1 <= 16 * 20:
            dp[x + 1][cnt] += dp[x][cnt]
        if x % 2 == 0 and cnt + 1 < 5:
            dp[x // 2][cnt + 1] += dp[x][cnt]
print(sum(dp[20]))

Решение с помощью рекурсии

from functools import lru_cache

@lru_cache(None)
def f(st, end, cnt):

    if (st > 20*16):
        return 0

    if (cnt > 4):
        return 0

    if (st == end):
        return 1 + f(st//2,end,cnt+1) + f(st+1, end, cnt)

    if (st%2 == 0):
        return f(st+1, end, cnt) + f(st//2, end, cnt+1)
    else:
        return f(st+1, end, cnt)


print(f(10,20,0))