Геральт копит чеканные монеты, количество которых записано на экране.
У него есть варианты, которым присвоены номера:
1. Прибавить 5 монет, убив утопца,
2. Прибавить 10 монет, выполнив заказ на призрака,
3. Увеличить количество монет в 2 раза, сыграв в гвинт.
Первый вариант учеличивает количество монет на 5, второй — на 10, третий — умножает количество монет на 2. Программа для Геральта из Ривии — это последовательность вариантов.
Геральту нужно накопить 100 монет, чтобы выкупить Лютика из плена эльфов.
Сколько существует программ, для которых при исходном количестве монет 15 является результатом 100 монет. При этом траектория вычислений содержит любимое число Геральта — 50 и не содержит числа 25 и 40? Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы 123 при исходном числе 7 траектория будет состоять из чисел 12, 22, 44.
Рекурсия:
def f(a,b):
if a > b or a == 25 or a == 40 :
return 0
if a == b:
return 1
if a < b:
return f(a + 5, b) + f(a + 10, b) + f(a * 2, b)
print(f(15, 50) * f(50, 100))
Динамика:
a = [0] * 101
a[15] = 1
for i in range(16, 101):
a[i] = a[i - 5] + a[i - 10] + a[i // 2] * (i % 2 == 0)
a[25] = 0
a[40] = 0
if i == 50:
for j in range(i):
a[j] = 0
print(a[100])