23.07 Количество результатов выполнения программ

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

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

def f(start, cnt_step, cnt_nch, max_step):
    global A
    if cnt_step == max_step and cnt_nch <= 3:
        A.add(start)
    if cnt_step > max_step or cnt_nch > 3:
        return
    f(start + 1, cnt_step + 1, cnt_nch + ((start + 1) % 2), max_step)
    f(start + 3, cnt_step + 1, cnt_nch + ((start + 3) % 2), max_step)
    f(start * 3, cnt_step + 1, cnt_nch + ((start * 3) % 2), max_step)

A = set()
f(2, 0, 0, 10)
print(len(A))

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

ans, otv = set(), set()
ans.add((2, 0))
for operations in range(10):
    can_get = set()
    for i in ans:
        ch, chet = i
        if chet + (ch + 1) % 2 <= 3:
            can_get.add((ch + 1, chet + (ch + 1) % 2))
        if chet + (ch + 3) % 2 <= 3:
            can_get.add((ch + 3, chet + (ch + 3) % 2))
        if chet + (ch * 3) % 2 <= 3:
            can_get.add((ch * 3, chet + (ch * 3) % 2))
    ans = can_get
for i in ans:
    a, b = i
    otv.add(a)
print(len(otv))