Задача #3552
Количество программ
(Герасимчук В.) Исполнитель преобразует число на экране. У исполнителя есть две команды, которые обозначены латинскими буквами:
A. Найти целую часть от деления на 3
B. Вычесть 3
Программа для исполнителя – это последовательность команд.
Сколько существует программ, для которых при исходном числе 68 результатом является число 4, при этом траектория вычислений не содержит одновременно 22 и 7?
Траектория вычислений программы – это последовательность результатов выполнения всех команд программы.
Например, для программы BBA при исходном числе 13 траектория состоит из чисел 10, 7, 2.
Войдите, чтобы история ответов и статистика сохранялись.
Решение
Ответ
18
def f(a, b):
if a == b:
return 1
elif a < b:
return 0
else:
return f(a // 3, b) + f(a - 3, b)
# нам подойдут все траектории кроме тех,
# которые содержат одновременно 22 и 7
ans1 = f(68, 4)
ans2 = f(68, 22) * f(22, 7) * f(7, 4)
print(ans1 - ans2)
