Задача #3549
Количество программ
(Герасимчук В.) Исполнитель преобразует число на экране. У исполнителя есть три команды, которые обозначены латинскими буквами:
A. Вычесть 1
B. Извлечь квадратный корень из числа
C. Извлечь кубический корень из числа
Команды B и C могут быть применены, если в результате извлечения корня получается целое число. Команда A может применяться к любым числам.
Программа для исполнителя – это последовательность команд.
Сколько существует программ, для которых при исходном числе 512 результатом является число 1, при этом траектория вычислений содержит число 8 или 64, но не оба числа одновременно?
Траектория вычислений программы – это последовательность результатов выполнения всех команд программы.
Например, для программы AC при исходном числе 126 траектория состоит из чисел 125, 5.
Решение
Ответ
a2 = [x**2 for x in range(2,40)]
a3 = [x**3 for x in range(2,40)]
def f(a, b, not_number):
if a == b:
return 1
elif a < b or a == not_number:
return 0
else:
f1 = f(a - 1, b, not_number)
if a in a2:
f2 = f(round(a ** (1/2)), b, not_number)
else:
f2 = 0
if a in a3:
f3 = f(round(a ** (1/3)), b, not_number)
else:
f3 = 0
return f1 + f2 + f3
# траектория содержит 8, но при этом не содержит 64
ans1 = f(512, 8, 64) * f(8, 1, 64)
# траектория содержит 64, но при этом не содержит 8
ans2 = f(512, 64, 8) * f(64, 1, 8)
print(ans1 + ans2)
