ALBLAK 52 и FRIENDLY THUG 52 NGG заперлись в питерской студии писать совместный альбом. На счётчике готовых треков пока $1$ , а в релиз надо выкатить $19$ , но обязательно дропнуть тизер на отметке $11$ . Исполнитель Вычислитель преобразует число, записанное на экране. У исполнителя есть три команды, которым присвоены номера:

Умножить на 3
Прибавить 2
Прибавить 3

Первая из них умножает число на экране на $3$ , вторая увеличивает его на $2$ , третья увеличивает его на $3$ . Программа для Вычислителя — это последовательность команд. Сколько существует таких программ, которые преобразуют исходное число $1$ в число $19$ и при этом траектория вычислений программы содержит число $11$ ?

Question

ALBLAK 52 и FRIENDLY THUG 52 NGG заперлись в питерской студии писать совместный альбом. На счётчике готовых треков пока $1$ , а в релиз надо выкатить $19$ , но обязательно дропнуть тизер на отметке $11$ . Исполнитель Вычислитель преобразует число, записанное на экране. У исполнителя есть три команды, которым присвоены номера:

Умножить на 3
Прибавить 2
Прибавить 3

Первая из них умножает число на экране на $3$ , вторая увеличивает его на $2$ , третья увеличивает его на $3$ . Программа для Вычислителя — это последовательность команд. Сколько существует таких программ, которые преобразуют исходное число $1$ в число $19$ и при этом траектория вычислений программы содержит число $11$ ?

Решение:

Решение на Python:

def F(x, y):
    if x > y:
        return 0

    if x == y:
        return 1

    if x < y:
        return F(x * 3, y) + F(x + 2, y) + F(x + 3, y)

print(F(1, 11) * F(11, 19))

Ответ: 52

Ответ:

52

Accepted Answer

52