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

Решение на 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))

Решение 1 (Рекурсия)

def f(day, count_drova, count_sajenec, days, tree):
    global minim
    if day > minim: # если день перешел минимальное количество дней,
        # то мы заканчиваем
        return
    i = 0
    while i < len(days): # массив дней, когда должны вырасти очередные деревья
        if days[i] == day:
            days.pop(i)
            a = tree.pop(i)
            count_drova += 10 * a # растет количество дров
            count_sajenec += 2 * a # растет количество саженцев
            i -= 1 # -1 тут и +1 ниже скомпенсируют удаленный элемент
        i += 1
    if count_drova >= 200 and day < minim:
        minim = day
        return
    for i in range(1, count_sajenec + 1):
        if i * 10 + count_drova > 200: # не нужно рассматривать варианты,
            # которые будут заведомо дольше чем мы хотим
            break
        # посадили i деревьев
        f(day + 1, count_drova, count_sajenec - i, days.copy() + [i + day],
          tree.copy() + [i])
minim = 10000000000
f(1, 0, 3, [], [])
print(minim)

Решение 2 (Динамика)

ans = []
ans.append((1, 0, 3))
# (сколько прошло дней, сколько есть дров, сколько есть саженцев)
otv = 10000000
for operations in range(1000):
    can_get = []
    for i in ans:
        days, wood, seed = i
        if wood >= 200:
            otv = min(otv, days)
            continue
        for j in range(1, seed + 1):  # сажаем j саженцев
            if j == 1:
                can_get.append((days + j, wood + j * 10, seed + j))
            else:
                can_get.append((days + j - 1, wood + j * 10, seed + j))
    if len(can_get) == 0:
        break
    ans = can_get
print(otv)

Решение 1 (Рекурсия)

def is_prime(n):
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            return False
    return n != 1

from functools import lru_cache
@lru_cache(None)
def f(st, fn, primes):
    global count
    if is_prime(st):
        primes += 1
    if st == fn:
        if primes < count:
            count = primes
        return
    if st > fn:
        return
    f(st + 1, fn, primes)
    f(st * 2 + 1, fn, primes)
    f(st * 2 - 1, fn, primes)
    f(st * 4 + 1, fn, primes)

count = 100000000000
f(10, 300, 0)
print(count)

Решение 2 (Динамика)

def is_prime(n):
    if n < 2:
        return 0
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            return 0
    return 1


a, primes = [10000000] * 301, [0] * 301
a[10] = 0
# для начала определим для каждого числа от 1 до 300
# простое оно, или нет
for i in range(2, 301):
    if is_prime(i):
        primes[i] = 1
# далее реализуем динамическое решение задачи
for i in range(10, 300):
    a[i + 1] = min(a[i + 1], a[i] + primes[i + 1])
    if i * 2 + 1 < 301:
        a[i * 2 + 1] = min(a[i * 2 + 1], a[i] + primes[i * 2 + 1])
    if i * 2 - 1 < 301:
        a[i * 2 - 1] = min(a[i * 2 - 1], a[i] + primes[i * 2 - 1])
    if i * 4 + 1 < 301:
        a[i * 4 + 1] = min(a[i * 4 + 1], a[i] + primes[i * 4 + 1])
print(a[300])

Решение 1 (Рекурсия)

from functools import lru_cache
@lru_cache(None)
def f(st, fn, en, comand):
    global count, ener
    if st == fn and en >= 0:
        if comand < count:
            count = comand
            ener = en
#если количество шагов совпало,
# то мы берем максимум энергии
        elif comand == count and en > ener:
            ener = en
        return # вылет из программы
    if en < 0:
        return
    f(st + 1, fn, en - 1, comand + 1)
    f(st + 2, fn, en - 3, comand + 1)
    f(st + 3, fn, en - 6, comand + 1)
count = 10000000
ener = -1
f(1, 25, 60, 0)
print(count, ener)

Решение 2 (Динамика)

ans = []
ans.append((1, 60, 0))
# (текущая ступенька, текущее кол-во энергии, кол-во сделанных ходов)
otv, mn_com = -100000000, 100000000
for operations in range(1000):
    can_get = []
    for i in ans:
        step, energy, go = i
        if (step > 25) or (energy < 0):
            continue
        if (step == 25) and (energy >= 0):
            if mn_com == go:  # берем минимум команд и максимум энергии
                mn_com = go
                otv = max(otv, energy)
                continue
            elif mn_com > go:
                mn_com = go
                otv = energy
                continue
        # все возможные ходы
        can_get.append((step + 1, energy - 1, go + 1))
        can_get.append((step + 2, energy - 3, go + 1))
        can_get.append((step + 3, energy - 6, go + 1))
    # если больше ходов нет, выходим из цикла
    if len(can_get) == 0:
        break
    ans = can_get.copy()
print(mn_com, otv)

Решение 1 (Рекурсия)

def is_prime(n):
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            return False
    return n > 1


def f(st, count_operation, set_prime):
    global count
    if count_operation > count:
        return  # выход из программы без действий
    if is_prime(st):
        set_prime.add(st)
    if len(set_prime) == 8:
        count = min(count, count_operation)
        return
    f(st + 3, count_operation + 1, set_prime.copy())
    f(st * 2 - 1, count_operation + 1, set_prime.copy())
    if st > 9:
        f(int(str(st)[::-1]) + 1, count_operation + 1, set_prime.copy())


count = 10000000000
f(2, 0, set())
print(count)

Решение 2 (Динамика)

def is_prime(n):
    if n < 2:
        return 0
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            return 0
    return 1


primes = [0] * 100000
# для начала определим для каждого числа от 1 до 99999
# простое оно, или нет
for i in range(2, 100000):
    if is_prime(i):
        primes[i] = 1
# далее реализуем динамическое решение задачи
ans = []
ans.append((2, 1))
otv, flag = 100000000, 0

for operations in range(1000):
    can_get = []
    for i in ans:
        a, pr = i
        if pr == 8:
            otv = operations
            flag = 1
            break
        can_get.append((a + 3, pr + primes[a + 3]))
        can_get.append((a * 2 - 1, pr + primes[a * 2 - 1]))
        if a > 9:
            s = str(a)
            s = s[::-1]
            new_num = int(s) + 1
            can_get.append((new_num, pr + primes[new_num]))
    if flag:
        break
    ans = can_get
                                                                                                     
                                                                                                     
print(otv)

Решение 1 (Рекурсия)

from functools import lru_cache
@lru_cache(None)
def f(st, fn):
    if st == fn:
        return 1
    if st[0] > fn[0] or st[1] > fn[1]:
        return 0
    c1 = f((st[0] + 2, st[1]), fn)
    c2 = f((st[0] * 2, st[1]), fn)
    c = [0] * (fn[1] - st[1] + 1)
    for i in range(1, fn[1] - st[1] + 1):
        c[i] = f((st[0], st[1] + i), fn)
    return c1 + c2 + sum(c)
print(f((1, 2), (12, 19)))

Решение 2 (Динамика)

dp = [[0] * 20 for i in range(13)]
dp[1][2] = 1
for x in range(1, 13):
    for y in range(2, 20):
        if x + 2 < 13:
            dp[x + 2][y] += dp[x][y]
        if x * 2 < 13:
            dp[x * 2][y] += dp[x][y]
        for to in range(y + 1, 20):
            dp[x][to] += dp[x][y]
print(dp[12][19])

Решение 1 (Рекурсия)

def f(st, fn):
    if st == fn:
        return 1
    if len(st) > len(fn):
        return 0
    x = f(st + "1", fn)
    if st.count("0") % 2 == 0:
        y = f(st + "0", fn)
    else:
        y = f("1" + st, fn)
    return x + y


print(f("1", "1011111"))

Решение 2 (Динамика)

def to_bin(n):  # перевод из десятичной СС в двоичную
    a = ""
    while n > 0:
        a = str(n % 2) + a
        n //= 2
    return a


# Если s="1010", то команда n=int(s, base=2) переводит число 1010
# из 2-й СС в 10-ю СС
a = [0] * 96
a[1] = 1
for i in range(1, 95):
    cur_num = to_bin(i)
    new_num = int(cur_num + "1", base=2)
    if new_num < 96:
        a[new_num] += a[i]
    chet_bit = cur_num.count("0") % 2
    if chet_bit:
        new_num = int("1" + cur_num, base=2)
    else:
        new_num = int(cur_num + "0", base=2)
    if new_num < 96:
        a[new_num] += a[i]
print(a[95])

Решение 1 (Рекурсия)

def f(start, finish, limits, visited):
    if (start == finish):
        return 1
    if (start < limits[0]) or (start > limits[1]):
        return 0
    if (start in visited):
        return 0
    vis = visited.copy()
    vis.add(start)
    x = f(start + 4, finish, limits, vis)
    y = f(start - 5, finish, limits, vis)
    return x + y
print(f(1, 20, (-20, 40), set()))

Решение 2 (Динамика)

ans = []
ans.append((1, set([1])))
otv = 0
for operations in range(1000):
    can_get = []
    for i in ans:
        a, vis = i
        vis_first = vis.copy()
        vis_second = vis.copy()
        if a == 20:
            otv += 1
            continue
        if ((a + 4) in vis) == 0 and (a + 4 <= 40):
            vis_first.add(a + 4)
            can_get.append((a + 4, vis_first))
        if ((a - 5) in vis) == 0 and (a - 5 >= -20):
            vis_second.add(a - 5)
            can_get.append((a - 5, vis_second))
    if len(can_get) == 0:
        break
    ans = can_get
print(otv)

Стоит сказать, что динамическое решение данной задачи будет занимать длительное время выполнения и большой объем памяти, в силу того, что для каждой программы из условия требуется хранить значений (текущее число, количество операций типа , количество операций типа , номер предыдущей операции и номер следующей операции). Поэтому рекомендуется решать эту задачу с помощью рекурсии.

from functools import lru_cache
@lru_cache(None)
def f(st, fn, count_2, count_3, old, next):
    if st == fn and count_3 > count_2 and old != 3:
        return True
    if st > fn:
        return False
    x = [0] * 3
    for i in range(3):
        if next == 1:
            x[i] = f(st + 1, fn, count_2, count_3, 1, i + 1)
        if next == 2:
            x[i] = f(st + old, fn, count_2 + 1, count_3, 2, i + 1)
        if next == 3:
            x[i] = f(st + i + 1, fn, count_2, count_3 + 1, 3, i + 1)
    return sum(x)
print(f(1, 24, 0, 0, 1, 1))

 

Стоит сказать, что динамическое решение получается довольно трудоемким и громоздким, поэтому рекомендуется использовать рекурсивную реализацию в данной задаче.

Решение 1 (Рекурсия)

def f(st, fn, count_2, count_3):
    if st == fn and count_3 > count_2:
        return True
    if st > fn:
        return False
    x = f(st + 3, fn, count_2, count_3)
    y = f(st * 2, fn, count_2 + 1, count_3)
    z = [0] * 10
    for i in range(10):
        z[i] = f(st * 10 + i, fn, count_2, count_3 + 1)
    return x + y + sum(z)
print(f(1, 48, 0, 0))

Решение 2 (Динамика)

ans = set()
ans.add((1, 0, 0))  # (куда пришли, сколько раз использовали вторую команду, раз использовали третью команду)
otv = 0
for operations in range(1000):
    can_get = set()
    for i in ans:
        a, cnt_2, cnt_3 = i
        if (a == 48) and (cnt_2 < cnt_3):
            otv += 1
            continue
        if a + 3 <= 48:
            can_get.add((a + 3, cnt_2, cnt_3))
        if a * 2 <= 48:
            can_get.add((a * 2, cnt_2 + 1, cnt_3))
        for j in range(9):
            new_numb = int(str(a) + str(j))
            if new_numb <= 48:
                can_get.add((new_numb, cnt_2, cnt_3 + 1))
    if len(can_get) == 0:
        break
    ans = can_get
print(otv)

Решение 1 (Рекурсия)

def f(st):
    global count
    if len(st) == 10:
        count += 1
        print(st)
    if len(st) < 10:
        f(st + "0") # приписать 0 справа
        f(st + st[::-1]) # приписать копию числа справа
count = 0
f("7")
print(count)

Решение 2 (Динамика)

ans = []
otv = 0
ans.append("7")
for operations in range(1000):
    can_get = []
    for i in ans:
        if len(i) == 10:
            otv += 1
        new_st = i + "0"
        if len(new_st) <= 10:
            can_get.append(new_st)
        new_st = i + i[::-1]
        if len(new_st) <= 10:
            can_get.append(new_st)
    if len(can_get) == 0:
        break
    ans = can_get

print(otv)

 

Решение 1 (Рекурсия)

def f(s, fi):
    if s > fi:
        return 0
    if s == fi:
        return 1
    return f(s + 2, fi) + f(s + 5, fi)
for i in range(6,100):
    if f(5, i) == 34:
        print(i)
        break

Решение 2 (Динамика)

a = [0] * 101
a[5] = 1
for i in range(6, 101):
    a[i] += a[i - 2] + a[i - 5]
print(a.index(34))

a = [0] * 300
a[0] = 10**20
a[1] = 0
for i in range(2, 300):
    x, y, z = 10**10, 10**10, 10**10
    x = a[i - 1] + 1
    if i >= 5:
        y = a[i - 5] + 1
    if i % 3 == 0:
        z = a[i // 3] + 1
    a[i] = min(x, y, z)
print(a[227])

a = [0] * 100
a[31] = 1
for i in range(32, 100 + 1):
    a[i] = a[i-2] + a[i-4] + a[i-5]
    if a[i] == 1001:
        print(i)
        break