Задача #1353

Количество программ

Сложнее ЕГЭ

(С. Чайкин) Исполнитель преобразует число на экране. У исполнителя есть три команды, которым обозначены латинскими буквами:

A. Прибавить 1
B. Умножить на 3
C. Прибавить 5

Программа для исполнителя – это последовательность команд.

Сколько существует программ, для которых при исходном числе 3 результатом является число 69, и при этом траектория вычислений содержит последовательность команд CAC?

Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы CBA при исходном числе 3 траектория состоит из чисел 8, 24, 26.

Ответ
Войдите, чтобы история ответов и статистика сохранялись.
Решение Нажми, чтобы открыть

Ответ

56729496
from functools import *

@lru_cache(None)
def f(s, e, p1='', p2='', valid=False):
    if s > e: return 0
    if s == e: return valid

    count = 0
    count += f(s+1, e, 'A', p1, valid)
    count += f(s*3, e, 'B', p1, valid)

    valid = valid or (p2 + p1 + 'C' == 'CAC')
    count += f(s+5, e, 'C', p1, valid)

    return count

print(f(3, 69))
Быстрый переход
Перейти к задаче