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

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

Решение на C++

void solve(){
    //dp[x][cnt] - количество программ приводящие в число x,
    //и при этом использовали ровно cnt операций второго типа
    vector<vector<int>> dp(16 * 20 + 1, vector<int>(5, 0));
    dp[10][0] = 1;
    for(int cnt = 0; cnt < 5; ++cnt){
        for(int x = 0; x <= 16 * 20; ++x){
            if(x + 1 < 16 * 20 + 1) //операция прибавить 1
         dp[x + 1][cnt] += dp[x][cnt];
            if(x % 2 == 0 && cnt + 1 < 5) //операция разделить на 2
                dp[x / 2][cnt + 1] += dp[x][cnt];
     }
    }
    cout << dp[20][0] + dp[20][1] + dp[20][2] + dp[20][3] + dp[20][4] << ’\n’;
}

Решение на Python

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))