Задача #3550
Количество программ
(Герасимчук В.) Исполнитель преобразует число на экране. У исполнителя есть три команды, которые обозначены латинскими буквами:
A. Вычесть 1
B. Вычесть 3
C. Найти целую часть от деления на 3
Программа для исполнителя – это последовательность команд.
Сколько существует программ, для которых при исходном числе 49 результатом является число 12, при этом траектория вычислений содержит как минимум два числа из множества {40, 30, 20}?
Траектория вычислений программы – это последовательность результатов выполнения всех команд программы.
Например, для программы ABB при исходном числе 13 траектория состоит из чисел 12, 9, 6.
Войдите, чтобы история ответов и статистика сохранялись.
Решение
Ответ
562318
def f(a, b, not_number):
if a == b:
return 1
elif a < b or a == not_number:
return 0
else:
return (f(a - 1, b, not_number) + f(a - 3, b, not_number) +
f(a // 3, b, not_number))
# содержит 40 и 30, но не содержит 20
ans1 = f(49, 40, 20) * f(40, 30, 20) * f(30, 12, 20)
# содержит 40 и 20, но не содержит 30
ans2 = f(49, 40, 30) * f(40, 20, 30) * f(20, 12, 30)
# содержит 20 и 30, но не содержит 40
ans3 = f(49, 30, 40) * f(30, 20, 40) * f(20, 12, 40)
# содержит 40, 30 и 20
ans4 = f(49, 40, -1) * f(40, 30, -1) * f(30, 20, -1) * f(20, 12, -1)
print(ans1 + ans2 + ans3 + ans4)
