23.03 Количество программ из A в B где траектория вычислений содержит число(-а)

Решение динамикой

Для решения будем использовать динамический подход. Основная идея состоит в том, чтобы создать массив, где каждый индекс соответствует числу на экране, а значение в ячейке показывает количество программ, которые приводят к этому числу. Алгоритм строится по следующей логике:

1. Инициализируем массив длиной 25 (так как нам нужно число 24) нулями, чтобы каждая ячейка изначально содержала 0.

2. Устанавливаем a[4] = 1, потому что начальное число — 4, и существует ровно один способ быть в этом положении.

3. Проходим по всем числам от 5 до 24 включительно. Для каждого числа считаем количество способов, которые его дают:

- Если можно применить команду «прибавить 1», добавляем значение ячейки a[i-1].

- Если можно применить команду «прибавить 5», добавляем значение ячейки a[i-5].

- Если число чётное, можно применить команду «умножить на 2» и добавить значение a[i//2].

4. После подсчёта для числа проверяем, является ли оно обязательным для траектории (числа 11 или 17). Если да, то обнуляем все предыдущие значения a[j] для , так как траектория должна содержать эти числа, и более ранние пути, которые не прошли через них, не учитываем.

5. После завершения цикла в ячейке a[24] будет количество всех программ, которые удовлетворяют условиям задачи.

# Создаем массив из 25 элементов, изначально все нули
a = [0] * 25
# Исходное число 4, существует один способ быть в этом состоянии
a[4] = 1
# Перебираем все числа от 5 до 24
for i in range(5, 25):
    # Считаем количество программ для текущего числа
    # прибавление 1
    # прибавление 5
    # умножение на 2 (только для четных чисел)
    a[i] = a[i - 1] + a[i - 5] + a[i // 2] * (i % 2 == 0)
    # Проверяем обязательные числа траектории
    if i == 11 or i == 17:
        # Обнуляем все предыдущие значения, чтобы учесть
        # обязательное прохождение через это число
        for j in range(i):
            a[j] = 0

# Выводим количество программ, приводящих от 4 к 24
print(a[24])

Решение аналитически

Пусть — количество программ, которые число 4 преобразуют в число . Тогда верно следующее утверждение:

— если число не делится на 2.

— если число делится на 2.

Заполним таблицу по данным формулам до 11:

По условию траектория должна проходить через число 11, значит , так как число 12 можно получить только из числа 11 (соблюдая траекторию). Заполним таблицу до 18:

Аналагично , так как число 19 можно получить только из 18, соблюдая траекторию. Заполним таблицу до конца:

Отсюда получаем ответ: 72.

Пусть — количество программ, которык число 2 преобразуют в число n. Тогда верно следующее утверждение:

— если число не делится на 2.

— если число делится на 2.

Заполним таблицу по данным формулам до 10:

По условию сказано, что траектория должна проходить через число 10, значит , так как число 11 мы можем получить (проходя через число 10) только командой 1. Заполним таблицу до конца:

Отсюда получаем ответ — 243.

Решение рекурсией

Идея решения заключается в использовании рекурсивной функции для подсчёта количества программ, преобразующих число в число . Мы рассматриваем все возможные действия на каждом шаге и суммируем количество способов, которые они дают. Так как траектория должна содержать число 10, решение разделяем на два этапа: сначала от 2 до 10, затем от 10 до 17, а итоговое количество программ равно произведению результатов обоих этапов.

Внутри функции проверяются условия:

1. Если текущее число стало больше целевого числа , дальнейшие действия невозможны и возвращаем 0.

2. Если текущее число совпало с целевым числом , найден один корректный путь, возвращаем 1.

3. Иначе рекурсивно вызываем функцию для трёх возможных команд: прибавить 1 (c+1), прибавить 3 (c+3) и умножить на 2 (c*2). Результаты этих вызовов суммируются, чтобы получить количество программ для текущего состояния.

# Определяем функцию f(c, m), которая считает количество программ
def f(c, m):
    # Если текущее число больше целевого,
    # дальнейшие действия невозможны
    if c > m:
        return 0
    # Если текущее число совпало с целевым,
    # найден один подходящий путь
    if c == m:
        return 1
    # Иначе считаем все возможные переходы:
    # прибавить 1, прибавить 3, умножить на 2
    return f(c+1, m) + f(c+3, m) + f(c*2, m)

# Считаем количество программ, которые проходят через 10
# сначала от 2 до 10, затем от 10 до 17, результат перемножаем
print(f(2,10) * f(10,17))

Пусть — количество программ, которые число 1 преобразуют в число n. Тогда верно следующее утверждение:

Заполним таблицу по данной формуле до 9:

По формуле , но по условию дано, что траектория должна проходить через число 9. Значит если мы будем проходить через 8, то условие будет не выполнено. Следовательно .

Заполним таблицу до конца:

Отсюда получаем искомое количество программ — 272.

Решение динамикой

Динамический способ решения заключается в том, чтобы подсчитать количество программ, которые ведут от начального числа 1 до конечного числа 14, с условием, что траектория обязательно проходит через число 9. Для этого создаем массив, где каждый индекс соответствует конкретному числу на экране, а значение в ячейке — количество программ, которые приводят к этому числу с учетом предыдущих шагов.

1. Создаем массив длиной 25 элементов, все элементы изначально равны 0. Каждый элемент массива a[i] будет обозначать количество программ, которые приводят к числу .

2. Устанавливаем a[4] = 1, так как это стартовое условие (сдвиг индексов в коде).

3. Проходим по всем числам от 5 до 24 (включительно) и считаем количество программ, которые могут привести к :

- прибавление 1 из ,

- прибавление 5 из ,

- деление на 2 из , только если делится на 2.

4. Если текущее число соответствует запрещенным значениям, через которые траектория не должна проходить (в данном коде это числа 11 и 17), обнуляем все предыдущие значения массива, чтобы исключить все пути, которые достигли этих чисел.

5. После прохождения всех чисел результат для конечного числа 14 хранится в ячейке a[24].

Таким образом, массив постепенно накапливает количество всех возможных программ для каждого числа, а специальные проверки позволяют учитывать условие прохождения через число 9 и исключения ненужных траекторий.

# Создаем массив длиной 25, все значения изначально равны 0
a = [0] * 25
# Устанавливаем исходное количество программ для числа 4
a[4] = 1
# Перебираем все числа от 5 до 24 включительно
for i in range(5, 25):
    # Считаем количество программ, которые приводят к числу i:
    # из i-1 командой "прибавить 1"
    # из i-5 командой "прибавить 5"
    # из i//2 командой "деление на 2", только если i четное
    a[i] = a[i - 1] + a[i - 5] + a[i // 2] * (i % 2 == 0)
    # Если текущее число равно запрещенному значению (11 или 17),
    # обнуляем все предыдущие значения массива, чтобы исключить эти траектории
    if i == 11 or i == 17:
        for j in range(i):
            a[j] = 0
# Выводим количество программ, которые приводят от 1 к 14 с условием прохождения через число 9
print(a[24])

Пусть — количество программ, которык число 3 преобразуют в число n. Тогда верно следующее утверждение:

— если число не делится на 3.

— если число делится на 3.

Заполним таблицу по данным формулам до 12:

По условию дано, что траектория проходит через число 12. Значит . Продлим таблицу до 18:

По условию сказано, что траектория должна проходить через числа 12 и 18. следовательно , так как число 19 нельзя получить напрямую из 12 или 18. Составим таблицу до конца:

Отсюда получаем ответ — 84.

Решение рекурсией

Определим функцию f(a, b), которая будет вызывать саму себя. Она подсчитает количество программ, преобразующих число a в b. Функция возвращает:

• 0, если a > b, так как такая траектория точно не будет подходящей и ее не нужно учитывать в подсчете количества траекторий;
• 1, если a == b, так как единица означает, что мы нашли путь, который число А может превратить в число B выполнив все условия задачи;
• сумму значений для трёх возможных переходов (+2, умножить на 3, +3), если a < b, так как такая траектория еще не нарушила условия задачи и может стать подходящей.

# Функция для подсчета количества программ преобразования a -> b
def f(c, m):
    if c > m: # Если число стало больше нужного
        return 0
    if c == m: # Если дошли до нужного числа
        return 1
    return f(c + 2, m) + f(c + 3, m) + f(c * 3, m) # Количество путей до текущего числа

print(f(3, 12) * f(12, 18) * f(18, 28)) # Найдем ответ по условию задачи. Умножение позволяет учесть, что в подсчётах участвует 12 и 18.

Пусть — количество программ, которые число 2 преобразует в число . Тогда верно следующее утверждение:

— если число не делится на 2 и на 3.

— если число делится на 2, но не делится на 3.

— если число делится на 3, но не делится на 2.

– если число делится и на 2, и на 3.

Заполним таблицу по данным формулам до 14:

По условию траектория должна проходить через число 14, значит , так как мы никак не можем получить число 15, чтобы траектория проходила через число 14. Продолжим заполнять таблицу:

Аналогично , так как число 30 никак нельзя получить, чтобы траектория проходила через число 29. Заполним таблицу до конца:

Отсюда получаем ответ: 5040.

Решение рекурсией

Определим функцию f(a, b), которая будет вызывать саму себя. Она подсчитает количество программ, преобразующих число a в b. Функция возвращает:

• 0, если a > b, так как такая траектория точно не будет подходящей и ее не нужно учитывать в подсчете количества траекторий;
• 1, если a == b, так как единица означает, что мы нашли путь, который число А может превратить в число B выполнив все условия задачи;
• сумму значений для трёх возможных переходов (умножить на 3, умножить на 2, +3, +2), если a < b, так как такая траектория еще не нарушила условия задачи и может стать подходящей.

# Функция для подсчета количества программ преобразования a -> b
def f(c, m):
    if c > m: # Если число стало больше нужного
        return 0
    if c == m: # Если дошли до нужного числа
        return 1
    return f(c + 2, m) + f(c + 3, m) + f(c * 3, m) + f(c * 2, m) # Количество путей до текущего числа

print(f(2, 14) * f(14, 29) * f(29, 38)) # Найдем ответ по условию задачи. Умножение позволяет учесть, что в подсчётах участвует 14 и 29.

Пусть — количество программ, которые число 2 преобразуют в число . Тогда верно следующее утверждение:

— если число не делится на 2 и на 3.

— если число делится на 2, но не делится на 3.

— если число делится на 3, но не делится на 2.

— если число делится и на 2, и на 3.

Используя данные формулы, заполним таблицу до 13:

По условию траектория должна проходить через число 13, значит , так как число 14 мы можем полчить только командой 1 из числа 13, чтобы траектория проходила через число 14. Продолжим заполнять таблицу:

Аналогично . Заполним таблицу до конца:

Отсюда получаем ответ – 129948.

Решение рекурсией

Определим функцию f(a, b), которая будет вызывать саму себя. Она подсчитает количество программ, преобразующих число a в b. Функция возвращает:

• 0, если a > b, так как такая траектория точно не будет подходящей и ее не нужно учитывать в подсчете количества траекторий;
• 1, если a == b, так как единица означает, что мы нашли путь, который число А может превратить в число B выполнив все условия задачи;
• сумму значений для трёх возможных переходов (+2, умножить на 2, умножить на 3, +1), если a < b, так как такая траектория еще не нарушила условия задачи и может стать подходящей.

# Функция для подсчета количества программ преобразования a -> b
def f(c, m):
    if c > m: # Если число стало больше нужного
        return 0
    if c == m: # Если дошли до нужного числа
        return 1
    return f(c + 2, m) + f(c + 1, m) + f(c * 3, m) + f(c * 2, m) # Количество путей до текущего числа

print(f(2, 13) * f(13, 19) * f(19, 27)) # Найдем ответ по условию задачи

Пусть — количество программ, которык число 2 преобразуют в число n. Тогда верно следующее утверждение:

— если число n не делится на 2.

Заполним таблицу по данной формуле до 10:

Заметим, что количество программ изменяется только на четных n. Значит следующее число, на котором изменится количество программ — 12. По условию нам дано, что траектория должна содержать число 10, значит — . Далее данное значение не будет меняться, так как тогда траектория не будет проходить через число 10.

В итоге получаем ответ — 7

Решение 2

def f(c,m):
    if c > m:
        return 0
    if c == m:
        return 1
    return f(c*2,m)+f(c+1,m)

print(f(2,10)*f(10,17))

Решение рекурсией

Идея рекурсивного решения заключается в разбиении задачи на два этапа: сначала считаем количество программ, которые приводят число 1 к числу 9, затем — от числа 9 к числу 15. Это нужно, чтобы учесть условие, что траектория содержит число 9.

Определяем функцию f(x, y), которая будет рекурсивно подсчитывать количество программ, приводящих число x к числу y. В функции:

- Если x == y, то найден корректный путь, возвращаем 1.

- Если x > y, дальнейшие преобразования невозможны, возвращаем 0.

- Иначе вызываем функцию рекурсивно для всех возможных команд: x + 1, x + 3, x * 2 и суммируем результаты.

Затем для учета условия про число 9 перемножаем результаты двух вызовов функции: f(1, 9) * f(9, 15).

# Определяем рекурсивную функцию f(x, y),
# которая считает количество программ, преобразующих x в y
def f(x, y):
    # Если текущее число достигло целевого числа y,
    # то найден один корректный путь, возвращаем 1
    if x == y:
        return 1
    # Если текущее число больше целевого,
    # дальнейшее преобразование не имеет смысла, возвращаем 0
    if x > y:
        return 0
    # В остальных случаях считаем все возможные переходы:
    # 1) прибавляем 1
    # 2) прибавляем 3
    # 3) умножаем на 2
    # и суммируем количество программ для этих вариантов
    else:
        return f(x + 1, y) + f(x + 3, y) + f(x * 2, y)

# Вычисляем количество программ, проходящих через число 9:
# сначала от 1 до 9, затем от 9 до 15
print(f(1, 9) * f(9, 15))

Решение динамикой

Идея динамического решения заключается в том, чтобы построить массив a, где индекс соответствует числу на экране, а значение — количеству программ, ведущих к этому числу.

- Инициализируем массив нулями: a = [0] * 16, так как нас интересуют числа от 1 до 15.

- Задаем a[1] = 1, так как стартуем с числа 1, существует ровно один способ быть в этом состоянии.

- Перебираем все числа от 2 до 15 включительно:

   - Для числа i добавляем количество программ, которые приходят из i-1 командой «прибавить 1».

   - Добавляем количество программ из i-3 командой «прибавить 3».

   - Добавляем количество программ из i//2 командой «умножить на 2», только если i делится на 2.

- Чтобы учесть условие, что траектория содержит число 9, после обработки i == 9 обнуляем все предыдущие значения массива a[j] для j < 9, так как они не учитывают прохождение через число 9.

После прохода по массиву, a[15] содержит количество программ, удовлетворяющих всем условиям.

# Создаем массив для чисел от 0 до 15, все элементы изначально равны 0
a = [0] * 16
# Исходное положение — число 1, существует один способ быть в этом состоянии
a[1] = 1
# Перебираем числа от 2 до 15 включительно
for i in range(2, 16):
    # Добавляем количество программ, приходящих из числа i-1
    # командой "прибавить 1", и из числа i-3 командой "прибавить 3"
    # и из числа i//2 командой "умножить на 2" (только если i делится на 2)
    a[i] += a[i - 1] + a[i - 3] + a[i // 2] * (i % 2 == 0)
    # После прохождения числа 9 обнуляем все предыдущие значения,
    # чтобы учитывать обязательное прохождение через число 9
    if i == 9:
        for j in range(i):
            a[j] = 0

# Выводим количество программ, которые ведут от 1 до 15 и проходят через 9
print(a[15])

Решение рекурсией

Идея рекурсивного решения заключается в построении функции f(x, y), которая возвращает количество программ, преобразующих число в число . Для реализации задаются следующие проверки и действия:

1. Если текущее число совпало с целевым числом , значит найден подходящий путь, возвращаем 1.

2. Если текущее число превысило , дальнейшие команды только увеличат , поэтому пути невозможны, возвращаем 0.

3. В остальных случаях функция вызывает саму себя для трёх вариантов действий: прибавить 2 (x+2), прибавить 3 (x+3), умножить на 2 (x*2). Количество программ для текущего равно сумме результатов этих вызовов.

Так как траектория должна содержать число 8, считаем отдельно пути от 3 до 8 и от 8 до 18. Общее количество программ равно произведению этих двух значений, так как для каждого пути из первой части можно выбрать любой путь из второй части.

# Определяем функцию f(x, y), которая считает количество программ от x до y
def f(x, y):
    # Если текущее число совпало с целевым, путь завершен успешно
    if x == y:
        return 1
    # Если текущее число больше целевого, путь невозможен
    if x > y:
        return 0
    # В остальных случаях считаем все варианты:
    # прибавить 2, прибавить 3, умножить на 2
    else:
        return f(x + 2, y) + f(x + 3, y) + f(x * 2, y)

# Считаем количество программ через число 8:
# сначала от 3 до 8, затем от 8 до 18, умножаем результаты
print(f(3, 8) * f(8, 18))

—

Решение динамикой

Идея динамического подхода состоит в том, чтобы построить массив, где индекс соответствует числу, а значение по этому индексу показывает количество способов добраться до этого числа.

1. Создаём массив a длиной 19 (от 0 до 18) и инициализируем его нулями.

2. Устанавливаем a[3]=1, так как стартуем из числа 3 и есть ровно один способ быть в нём.

3. Проходим циклом по всем числам от 4 до 18. Для каждого числа i:

- добавляем количество программ из числа i-2, так как команда "прибавить 2"ведёт к i;

- добавляем количество программ из числа i-3, так как команда "прибавить 3"ведёт к i;

- если i чётное, добавляем количество программ из i//2, так как команда "умножить на 2"ведёт к i;

4. Если i = 8, значит мы достигли числа, через которое должна проходить траектория. Тогда обнуляем все значения для индексов меньше 8, чтобы учесть только пути, которые прошли через 8.

После завершения цикла значение a[18] даёт количество программ от 3 до 18, проходящих через число 8.

# Создаем массив для чисел от 0 до 18, все значения изначально 0
a = [0] * 19
# Стартуем из числа 3, только один путь до него
a[3] = 1
# Перебираем числа от 4 до 18 включительно
for i in range(4, 19):
    # Считаем все способы добраться до i:
    # из i-2 командой +2
    # из i-3 командой +3
    # из i//2 командой *2, только если i четное
    a[i] += a[i - 2] + a[i - 3] + a[i // 2] * (i % 2 == 0)
    # Если достигли числа 8, очищаем все предыдущие пути,
    # чтобы гарантировать прохождение через 8
    if i == 8:
        for j in range(i):
            a[j] = 0

# Количество программ от 3 до 18 через число 8
print(a[18])

Решение рекурсией

Идея рекурсивного решения заключается в том, чтобы построить функцию f(x, y), которая подсчитывает количество программ, преобразующих число в число .

- Если текущее число совпадает с целевым , возвращаем 1, так как найден корректный путь.

- Если больше , возвращаем 0, так как дальнейшие операции не могут привести к уменьшению числа.

- В остальных случаях функция рекурсивно вызывает сама себя для трёх вариантов команд: , и , суммируя результаты этих вызовов, чтобы получить общее количество программ.

Так как траектория должна содержать число 22, решение разбивается на два этапа: из 3 в 22 и из 22 в 35. Итоговое количество программ равно произведению результатов двух этапов, так как для каждого пути первой части можно использовать любой путь второй части.

# Функция для подсчета количества программ из x в y
def f(x, y):
    # Если текущее число совпало с целевым, возвращаем 1
    if x == y:
        return 1
    # Если текущее число превысило целевое, путь невозможен
    if x > y:
        return 0
    # Суммируем количество программ для всех трех команд
    return f(x + 3, y) + f(x + 4, y) + f(x * 2, y)

# Вычисляем общее количество программ через число 22
print(f(3, 22) * f(22, 35))

—

Решение динамикой

Динамический способ решения заключается в построении массива a, где индекс соответствует числу на экране, а значение a[i] — количество программ, которые преобразуют исходное число в число .

1. Инициализируем массив нулями и задаём a[3] = 1, так как начинаем с числа 3.

2. Перебираем все числа от 3 до 22 включительно. Для каждого числа прибавляем количество программ к числам , и , чтобы учесть все возможные команды. Таким образом, в массиве к моменту достижения числа 22 будут корректно подсчитаны все пути из 3 в 22.

- После этого необходимо обнулить все значения в массиве, кроме a[22]. Это делается потому, что траектория должна содержать число 22: все пути, которые не достигли числа 22, не удовлетворяют условию, и их нельзя учитывать на следующем этапе.

3. Далее перебираем числа от 22 до 35 включительно, применяя те же команды. На этом этапе a[i] учитывает только пути, которые начинаются из числа 22, гарантируя, что траектория обязательно проходит через него.

4. В конце a[35] содержит количество программ, которые из 3 ведут в 35 и при этом проходят через 22.

# Создаем массив из 1000 элементов, все значения изначально 0
a = [0] * 1000
# Начальное число 3, существует ровно один способ быть в этом положении
a[3] = 1

# Первый этап: от 3 до 22
for i in range(3, 22 + 1):
    # Для каждого числа добавляем количество программ к числам,
    # которые получаются применением каждой команды
    a[i + 3] += a[i]
    a[i + 4] += a[i]
    a[i * 2] += a[i]

# Обнуляем все числа, кроме 22, чтобы следующие этапы учитывали только траектории,
# проходящие через 22
for i in range(1000):
    if i != 22:
        a[i] = 0

# Второй этап: от 22 до 35
for i in range(22, 35 + 1):
    # Применяем все три команды и суммируем количество программ
    a[i + 3] += a[i]
    a[i + 4] += a[i]
    a[i * 2] += a[i]

# Выводим итоговое количество программ
print(a[35])

Решение рекурсией

Решение рекурсией строится на определении функции f(x, y), которая вычисляет количество программ, преобразующих число в число . Алгоритм реализуется следующим образом:

1. Сначала проверяем условие x == y. Если текущее число равно целевому, значит найден один корректный путь, поэтому возвращаем 1.

2. Если текущее число превысило целевое (x > y), дальнейшие операции только увеличат число, а значит нельзя достичь . В этом случае возвращаем 0.

3. Если ни одно из условий не выполнено, выполняем три рекурсивных вызова:

- f(x+1, y) — учитывает вариант применения команды "прибавить 1";

- f(x+4, y) — учитывает вариант применения команды "прибавить 4";

- f(x*4, y) — учитывает вариант применения команды "умножить на 4";

Затем складываем результаты всех трёх вызовов, чтобы получить общее количество программ из в .

Так как траектория должна содержать число 11, общее количество программ вычисляется как произведение количества программ из 3 в 11 и количества программ из 11 в 27: f(3, 11) * f(11, 27).

# Определяем функцию f(x, y), которая считает количество программ
def f(x, y):
    # Если текущее число равно целевому числу,
    # значит найден один корректный путь
    if x == y:
        return 1
    # Если текущее число стало больше целевого,
    # дальнейшие команды не помогут, возвращаем 0
    if x > y:
        return 0
    # В остальных случаях считаем все возможные переходы:
    # +1, +4 и *4, и суммируем количество путей
    else:
        return f(x + 1, y) + f(x + 4, y) + f(x * 4, y)

# Вычисляем общее количество программ, проходящих через число 11
# Сначала количество программ от 3 до 11
# Потом количество программ от 11 до 27
# Произведение этих двух чисел даст итоговое количество
print(f(3, 11) * f(11, 27))

—

Решение динамикой

Динамический способ строится на последовательном подсчёте количества программ для каждого числа с использованием массива. Алгоритм реализуется следующим образом:

1. Создаём массив a достаточного размера, заполненный нулями. Каждая ячейка с индексом будет хранить количество программ, которые приводят к числу .

2. В ячейку с индексом 3 записываем 1, так как начинаем с числа 3.

3. Заполняем массив для чисел от 3 до 11 включительно:

- Для каждого числа i добавляем a[i] к a[i+1], учитывая команду "прибавить 1";

- Добавляем a[i] к a[i+4], учитывая команду "прибавить 4";

- Добавляем a[i] к a[i*4], учитывая команду "умножить на 4".

4. После первого этапа обнуляем все элементы массива, кроме элемента с индексом 11, так как траектория должна обязательно содержать число 11.

5. Второй этап: для чисел от 11 до 27 выполняем аналогичные шаги, суммируя количество программ по каждой команде.

6. В итоге элемент a[27] содержит количество программ от 3 до 27 через число 11.

# Создаем массив достаточного размера и заполняем нулями
a = [0] * 1000
# Начальное число 3, только один способ быть в этом состоянии
a[3] = 1

# Первый этап: считаем количество программ от 3 до 11
for i in range(3, 11 + 1):
    # Переход командой +1
    a[i + 1] += a[i]
    # Переход командой +4
    a[i + 4] += a[i]
    # Переход командой *4
    a[i * 4] += a[i]

# Обнуляем все значения кроме ячейки 11, так как траектория должна пройти через 11
for i in range(1000):
    if i != 11:
        a[i] = 0

# Второй этап: считаем количество программ от 11 до 27
for i in range(11, 27 + 1):
    # Переход командой +1
    a[i + 1] += a[i]
    # Переход командой +4
    a[i + 4] += a[i]
    # Переход командой *4
    a[i * 4] += a[i]

# Результат: количество программ, приводящих от 3 к 27 через 11
print(a[27])

Решение рекурсией

Идея рекурсивного решения заключается в построении функции f(x, y), которая вычисляет количество программ, преобразующих число в число . Алгоритм работает следующим образом:

1. Если текущее число x равно целевому y, значит найден один корректный путь. Функция возвращает 1.

2. Если текущее число x больше y, дальнейшие команды только увеличат число, поэтому достичь y невозможно. Функция возвращает 0.

3. В остальных случаях функция вызывает саму себя трижды, соответствуя трём командам:

- f(x + 3, y) — прибавить 3;

- f(x + 4, y) — прибавить 4;

- f(x * 2, y) — умножить на 2.

Суммируем результаты этих вызовов, чтобы получить общее количество программ.

Так как траектория должна содержать число 22, общее количество программ вычисляется как произведение количества программ от 3 до 22 и от 22 до 35: f(3, 22) * f(22, 35).

# Определяем функцию f(x, y), которая считает количество программ
def f(x, y):
    # Если текущее число равно целевому, найден корректный путь
    if x == y:
        return 1
    # Если текущее число превысило целевое, дальнейшие команды не помогут
    if x > y:
        return 0
    # В остальных случаях считаем все возможные переходы:
    # +3, +4, *2, и суммируем количество программ
    else:
        return f(x + 3, y) + f(x + 4, y) + f(x * 2, y)

# Вычисляем общее количество программ, проходящих через число 22
# Сначала количество программ от 3 до 22
# Потом количество программ от 22 до 35
# Произведение этих чисел даст итоговое количество
print(f(3, 22) * f(22, 35))

—

Решение динамикой

Динамический способ строится на последовательном подсчёте количества программ для каждого числа с использованием массива. Алгоритм реализуется следующим образом:

1. Создаём массив a размера 36, заполненный нулями. Каждая ячейка a[i] хранит количество программ, приводящих к числу .

2. В ячейку a[3] записываем 1, так как начинаем с числа 3.

3. Для всех чисел от 4 до 35 считаем количество программ:

- a[i] = a[i-3] + a[i-4] + a[i//2] * (i % 2 == 0) — учитываем команды "прибавить 3 "прибавить 4"и "умножить на 2"(умножение возможно только для чётных чисел).

4. Когда достигаем числа 22, обнуляем все предыдущие значения массива (a[j] = 0 для всех ), чтобы гарантировать, что траектория проходит через 22.

5. После завершения цикла элемент a[35] содержит количество программ, которые приводят от 3 к 35 через число 22.

# Создаем массив размера 36 и заполняем нулями
a = [0] * 36
# Начальное число 3, только один способ быть в этом состоянии
a[3] = 1

# Перебираем все числа от 4 до 35 и считаем количество программ
for i in range(4, 36):
    # Команда прибавить 3
    a[i] = a[i - 3] + a[i]
    # Команда прибавить 4
    a[i] += a[i - 4]
    # Команда умножить на 2 (только для четных чисел)
    if i % 2 == 0:
        a[i] += a[i // 2]

    # Если достигли числа 22, обнуляем все предыдущие значения,
    # чтобы траектория обязательно содержала число 22
    if i == 22:
        for j in range(i):
            a[j] = 0

# Результат: количество программ от 3 до 35 через 22
print(a[35])

Решение динамикой

Динамический способ решения заключается в подсчёте количества программ, которые преобразуют каждое число по порядку от исходного до целевого, с учётом того, что траектория должна содержать определённое число (в данном случае 11).

1. Создаём массив a длиной 28 (так как нам нужно дойти до числа 27) и заполняем его нулями. Каждый элемент массива a[i] будет хранить количество программ, которые приводят к числу .

2. В ячейку с индексом 3 записываем 1, так как начинаем с числа 3, и только один способ быть в этом состоянии.

3. Перебираем числа от 4 до 27 включительно (for i in range(4, 28)), и для каждого числа выполняем следующие действия:

- a[i] = a[i - 1] + a[i - 4] + a[i // 4] * (i % 4 == 0) — суммируем количество программ для переходов из чисел , и (для кратных 4), что соответствует применению команд +1, +4 и *4;

4. Когда достигнуто число 11, необходимо обнулить все предыдущие значения (for j in range(i): a[j] = 0), чтобы гарантировать, что траектория обязательно проходит через число 11.

5. После завершения цикла элемент a[27] будет содержать количество программ, преобразующих число 3 в число 27, проходя через число 11.

# Создаем массив для хранения количества программ до числа 27
a = [0] * 28

# Начальное число 3, только один способ быть в этом состоянии
a[3] = 1

# Заполняем массив для чисел от 4 до 27
for i in range(4, 28):
    # Количество программ, приводящих к числу i, равно сумме программ,
    # которые приводят к i-1, i-4 и i//4 (если i кратно 4)
    a[i] = a[i - 1] + a[i - 4] + a[i // 4] * (i % 4 == 0)

    # Если достигнуто число 11, обнуляем все предыдущие значения,
    # чтобы траектория проходила через 11
    if i == 11:
        for j in range(i):
            a[j] = 0

# Выводим количество программ, приводящих к числу 27 через 11
print(a[27])

Решение рекурсией

Идея рекурсивного решения заключается в том, чтобы построить функцию, которая считает количество программ, приводящих число к числу , учитывая, была ли достигнута промежуточная цель (число 10). Функция принимает три аргумента: текущее число , целевое число и логический флаг flag, показывающий, встречалось ли число 10 на пути.

На каждом шаге проверяются условия:

- Если текущее число больше целевого , дальнейшие команды не могут привести к цели, поэтому возвращаем 0.

- Если текущее число равно 10, устанавливаем флаг flag=True, чтобы отметить достижение промежуточной цели.

- Если текущее число равно и флаг flag установлен, значит найден корректный путь, возвращаем 1.

- В остальных случаях функция рекурсивно вызывает себя трижды: добавляет 1 (s+1), добавляет 2 (s+2) и умножает на 3 (s*3). Сумма этих вызовов дает общее количество программ для текущего состояния.

Вызов функции f(2, 13, False) запускает рекурсивный перебор всех возможных последовательностей команд с учетом условия прохождения через число 10.

# Определяем функцию f(s, fi, flag) для подсчета количества программ
def f(s, fi, flag):
    # Если текущее число превысило целевое, путь невозможен
    if s > fi:
        return 0
    # Если текущее число равно 10, отмечаем достижение промежуточной цели
    if s == 10:
        flag = True
    # Если текущее число равно целевому и флаг установлен, найден корректный путь
    if s == fi and flag:
        return 1
    # В остальных случаях считаем все возможные варианты действий:
    # прибавить 1, прибавить 2, умножить на 3
    return f(s + 1, fi, flag) + f(s + 2, fi, flag) + f(s * 3, fi, flag)

# Запускаем функцию с начальным числом 2, целевым числом 13 и флагом False
print(f(2, 13, False))

—

Решение динамикой

Идея динамического решения заключается в последовательном заполнении массива, где каждый индекс соответствует числу, а значение — количеству программ, которые приводят от начального числа 2 к этому числу. При этом необходимо учитывать, что число 10 должно быть достигнуто.

- Создаем массив a длиной 14 (чтобы включить число 13), все значения изначально равны 0.

- Начальное положение: a[2] = 1, так как есть ровно один способ быть в числе 2.

- Для каждого числа от 3 до 13 последовательно вычисляем количество программ:

1. Добавляем a[i-1] — количество программ, приведших к , если применить команду "прибавить 1".

2. Добавляем a[i-2] — количество программ, приведших к , если применить команду "прибавить 2".

3. Если делится на 3, добавляем a[i//3] — количество программ, приведших к , если применить команду "умножить на 3".

- Когда индекс достигает 10, обнуляем все предыдущие значения массива (от 0 до 9), так как для корректного пути число 10 должно быть достигнуто, и все пути, которые не проходят через 10, больше не учитываются.

- В конце массив a[13] содержит количество программ, которые приводят от 2 к 13, проходя через 10.

# Создаем массив из 14 элементов, все значения равны 0
a = [0] * 14
# Начальное положение: только один способ быть в числе 2
a[2] = 1
# Перебираем все числа от 3 до 13
for i in range(3, 14):
    # Добавляем количество программ, которые пришли командой +1 и +2
    a[i] += a[i - 1] + a[i - 2]
    # Если число делится на 3, добавляем количество программ, пришедших командой *3
    if i % 3 == 0:
        a[i] += a[i // 3]
    # Если текущее число 10, обнуляем все предыдущие значения,
    # так как траектория должна содержать число 10
    if i == 10:
        for j in range(i):
            a[j] = 0

# Выводим количество программ, которые приводят к числу 13, проходя через 10
print(a[13])

Решение рекурсией

Идея рекурсивного решения заключается в том, чтобы построить функцию f(x, y), которая считает количество программ, преобразующих число в число . Функция работает следующим образом:

1. Если текущее число совпало с целевым , возвращаем , так как найден один корректный путь.

2. Если текущее число превысило , возвращаем , так как дальнейшие преобразования не могут привести к результату.

3. В остальных случаях функция вызывает саму себя дважды: первый раз с аргументом , что соответствует команде «прибавить 3», второй раз с аргументом , что соответствует команде «умножить на 2». Результаты этих двух вызовов суммируются, чтобы получить общее количество программ.

Так как требуется, чтобы траектория обязательно проходила через число 30, общее количество программ вычисляется как произведение f(12, 30) и f(30, 96).

# Определяем рекурсивную функцию f(x, y)
def f(x, y):
    # Если текущее число достигло целевого значения,
    # возвращаем 1, так как найден корректный путь
    if x == y:
        return 1
    # Если текущее число превысило целевое,
    # возвращаем 0, так как путь невозможен
    if x > y:
        return 0
    # В остальных случаях считаем количество программ,
    # пробуем оба варианта: прибавить 3 или умножить на 2
    else:
        return f(x + 3, y) + f(x * 2, y)

# Вычисляем и выводим общее количество программ,
# проходящих через число 30
print(f(12, 30) * f(30, 96))

—

Решение динамикой

Идея динамического подхода состоит в том, чтобы создать массив a, где индекс соответствует числу, а значение по индексу — количество способов добраться до этого числа из числа 12.

1. Создаём массив длиной 97, изначально заполненный нулями, и записываем в ячейку с индексом 12 значение 1, так как стартуем с числа 12.

2. Проходим циклом по всем числам от 15 до 96 включительно. Для каждого числа :

- прибавляем значение из ячейки , так как к можно прийти командой «прибавить 3»;

- если чётное, добавляем значение из ячейки , так как к можно прийти командой «умножить на 2».

3. После того как мы дошли до числа 30, обнуляем все значения до 30, так как траектория должна обязательно проходить через 30, и предыдущие пути нельзя учитывать.

4. После заполнения массива, значение в ячейке с индексом 96 будет равно количеству программ, удовлетворяющих условию задачи.

# Создаем массив длиной 97, все элементы изначально равны 0
a = [0]*97
# В ячейку с индексом 12 записываем 1, так как стартуем с числа 12
a[12] = 1
# Перебираем числа от 15 до 96 включительно
for i in range(15, 97):
    # Количество способов добраться до i увеличиваем на:
    # a[i-3] - путь командой "прибавить 3"
    # a[i//2] * (i % 2 == 0) - путь командой "умножить на 2", только если i четное
    a[i] += a[i-3] + a[i//2] * (i % 2 == 0)
    # Если достигли числа 30, обнуляем все предыдущие значения,
    # так как траектория должна обязательно проходить через 30
    if i == 30:
        for j in range(30):
            a[j] = 0

# Выводим количество программ, которые приводят от 12 к 96,
# проходя через 30
print(a[96])

Решение рекурсией

Рекурсивный способ решения заключается в определении функции f(start, finish), которая подсчитывает количество программ, преобразующих число start в число finish. Функция реализует три условия:

- Если текущее число start равно finish, значит найден корректный путь, возвращаем 1.

- Если текущее число превышает finish, дальнейшее применение команд невозможно, возвращаем 0.

- В остальных случаях функция вызывает сама себя трижды: f(start+1, finish) (команда "прибавь 1"), f(start+5, finish) (команда "прибавь 5") и f(start*start, finish) (команда "возвести в квадрат"). Сумма этих трёх вызовов даёт общее количество программ для данного промежутка.

Поскольку траектория должна содержать число 5, решаем задачу по частям: сначала считаем количество программ от 2 до 5, затем от 5 до 26, и перемножаем результаты, так как каждый путь первой части может сочетаться с любым путём второй части.

# Функция для подсчета количества программ от start до finish
def f(start, finish):
    # Если текущее число равно целевому, найден один путь
    if start == finish:
        return 1
    # Если текущее число превысило целевое, пути нет
    if start > finish:
        return 0
    # Считаем все возможные переходы: +1, +5, возведение в квадрат
    return f(start + 1, finish) + f(start + 5, finish) + f(start * start, finish)

# Считаем количество программ от 2 до 5 и от 5 до 26
# Перемножаем результаты для учета условия о траектории
print(f(2, 5) * f(5, 26))

—

Решение динамикой

Динамический способ решения заключается в том, чтобы постепенно вычислять количество программ для всех чисел, начиная с исходного числа, и хранить эти значения в массиве. Каждый индекс массива соответствует числу на экране, а значение в ячейке — количество программ, которые приводят к этому числу.

1. Создаем массив a большого размера (например, 10000 элементов) и инициализируем его нулями.

2. В ячейку с индексом 2 записываем 1, так как мы начинаем с числа 2.

3. Перебираем все числа от 2 до 26 (целевое число включительно). На каждом шаге делаем следующее:

- Если текущее число равно 5 (обязательное число в траектории), обнуляем все будущие значения массива от 6 до 26, чтобы учесть требование, что 5 должна обязательно встретиться.

- Для каждого числа добавляем количество способов для текущего числа в ячейки i+1, i+5 и i*i, соответствующие действиям команд "прибавь 1 "прибавь 5"и "возвести в квадрат". Это позволяет аккумулировать все возможные траектории до каждого числа.

4. После завершения цикла в ячейке с индексом 26 хранится общее количество программ, которые начинаются с 2, проходят через 5 и заканчиваются на 26.

# Создаем массив для подсчета количества программ
a = [0] * 10000
# Исходное число 2 — один способ быть в этом состоянии
a[2] = 1

# Проходим по всем числам от 2 до 26
for i in range(2, 26):
    # Если текущее число равно обязательному числу 5
    if i == 5:
        # Обнуляем все будущие числа до 26,
        # чтобы учесть условие прохождения через 5
        for j in range(6, 27):
            a[j] = 0
    # Добавляем текущие способы в следующие числа согласно командам
    a[i + 1] += a[i]   # команда "прибавь 1"
    a[i + 5] += a[i]   # команда "прибавь 5"
    a[i * i] += a[i]   # команда "возвести в квадрат"

# Количество программ, удовлетворяющих условиям, хранится в a[26]
print(a[26])

Решение рекурсией

Идея рекурсивного решения заключается в том, чтобы определить функцию, которая подсчитывает количество программ, преобразующих текущее число в целевое число , учитывая, была ли достигнута промежуточная цель (число 9).

- Функция принимает три аргумента: — текущее число, — целевое число, — логическая переменная, которая отмечает, достигнуто ли число 9.

- На каждом шаге проверяем условия:

- Если равно 9, устанавливаем , чтобы отметить достижение промежуточной цели.

- Если равно и установлен, значит найден корректный путь, возвращаем 1.

- Если больше , дальнейшие команды не смогут достичь цели, возвращаем 0.

- В остальных случаях функция рекурсивно вызывает себя трижды: (команда 1), (команда 2), (команда 3). Сумма этих вызовов дает общее количество программ для текущего состояния.

Вызов функции f(3, 14) запускает рекурсивный перебор всех возможных последовательностей команд, проходящих через число 9.

# Определяем рекурсивную функцию f(s, fi, flag) для подсчета программ
def f(s, fi, flag = False):
    # Если текущее число равно 9, отмечаем, что промежуточная цель достигнута
    if s == 9:
        flag = True
    # Если текущее число равно целевому и флаг установлен, найден корректный путь
    if (s == fi) and (flag):
        return 1
    # Если текущее число больше целевого, путь невозможен
    if s > fi:
        return 0
    # В остальных случаях считаем все возможные действия: +1, +2, *3
    return f(s + 1, fi, flag) + f(s + 2, fi, flag) + f(s * 3, fi, flag)

# Запуск функции с начальным числом 3 и целевым числом 14
print(f(3, 14))

—

Решение динамикой

Идея динамического решения заключается в последовательном вычислении количества программ для каждого числа от начального до целевого с учетом условия прохождения через число 9.

- Создаем массив a длиной 15 (чтобы включить число 14), изначально все элементы равны 0.

- Начальное положение: a[3] = 1, так как существует ровно один способ быть в числе 3.

- Для чисел от 4 до 9 заполняем массив:

1. a[i] += a[i-1] — добавляем количество программ, приведших к командой +1.

2. a[i] += a[i-2] — добавляем количество программ, приведших к командой +2.

3. Если делится на 3, a[i] += a[i//3] — добавляем количество программ, пришедших командой *3.

- После заполнения чисел до 9 обнуляем все элементы массива с индексами от 1 до 8, так как траектория должна содержать число 9, и пути, которые не проходят через 9, больше не учитываются.

- Для чисел от 10 до 14 повторяем процесс суммирования значений для переходов +1, +2 и *3.

- В конце a[14] содержит количество программ, которые преобразуют 3 в 14 и проходят через число 9.

# Создаем массив из 15 элементов, все значения равны 0
a = [0] * 15
# Начальное положение: один способ быть в числе 3
a[3] = 1
# Заполняем массив для чисел от 4 до 9
for i in range(4, 10):
    a[i] += a[i - 1]  # прибавляем количество программ из i-1
    a[i] += a[i - 2]  # прибавляем количество программ из i-2
    if i % 3 == 0:
        a[i] += a[i // 3]  # прибавляем количество программ из i//3, если делится на 3
# Обнуляем элементы до числа 9, чтобы учитывать условие прохождения через 9
for i in range(1, 9):
    a[i] = 0
# Заполняем массив для чисел от 10 до 14
for i in range(10, 15):
    a[i] += a[i - 1]  # прибавляем количество программ из i-1
    a[i] += a[i - 2]  # прибавляем количество программ из i-2
    if i % 3 == 0:
        a[i] += a[i // 3]  # прибавляем количество программ из i//3, если делится на 3
# Выводим количество программ, которые приводят к числу 14, проходя через 9
print(a[14])

Решение рекурсией

Рекурсивное решение основывается на разбиении задачи на два этапа: подсчет всех программ, которые преобразуют число 2 в 10, и всех программ, которые преобразуют число 10 в 30. Общее количество программ равно произведению этих двух чисел, так как каждая траектория до 10 может соединяться с любой траекторией от 10 до 30.

- Определяем рекурсивную функцию f(x, y), которая подсчитывает количество программ, преобразующих текущее число в целевое .

- Условия проверки внутри функции:

1. Если равно , возвращаем 1, так как путь успешно завершен.

2. Если больше , возвращаем 0, так как дальнейшее выполнение команд не приведет к цели.

3. Иначе выполняем три рекурсивных вызова: (команда 3), (команда 1), (команда 2) и возвращаем их сумму.

Таким образом, f(2,10) подсчитает все пути от 2 до 10, а f(10,30) — от 10 до 30. Их произведение даст итоговое количество программ.

# Рекурсивная функция подсчета программ от x до y
def f(x, y):
    # Если текущее число равно целевому, найден корректный путь
    if x == y:
        return 1
    # Если текущее число больше целевого, путь невозможен
    if x > y:
        return 0
    else:
        # В остальных случаях считаем все возможные действия: +1, +3, *2
        return f(x + 1, y) + f(x + 3, y) + f(x * 2, y)

# Общее количество программ равно произведению способов до 10 и от 10 до 30
print(f(2, 10) * f(10, 30))

—

Решение динамикой

Динамический способ решения позволяет последовательно подсчитывать количество программ для каждого числа, используя массив для хранения промежуточных результатов.

- Создаем массив a длиной 93 (выбран с запасом, 31*3) для всех чисел до 30.

- Инициализируем a[2] = 1, так как существует ровно один способ быть в числе 2.

- Проходим по массиву чисел от 2 до 29:

1. Если текущее число равно 10, сохраняем значение a[i] во вспомогательную переменную b, затем обнуляем весь массив и восстанавливаем только a[i]=b, чтобы исключить траектории, не проходящие через 10.

2. Для каждого числа добавляем количество программ в следующие позиции: a[i+1] += a[i], a[i+3] += a[i], a[i*2] += a[i], чтобы учесть все три команды. - После завершения итерации массив a[30] содержит количество программ, преобразующих число 2 в 30 и проходящих через число 10.

# Создаем массив для хранения количества программ до чисел до 30
a = [0] * 31 * 3
# Начальное положение: один способ быть в числе 2
a[2] = 1
# Перебираем числа от 2 до 29
for i in range(2, 30):
    # Если достигнуто число 10, сохраняем текущее значение и обнуляем массив
    if i == 10:
        b = a[i]      # Сохраняем количество программ, достигших 10
        a = [0] * 31 * 3  # Обнуляем все элементы массива
        a[i] = b      # Восстанавливаем значение для числа 10
    # Обновляем количество программ для следующего числа командой +3
    a[i + 3] += a[i]
    # Обновляем количество программ для числа при умножении на 2
    a[i * 2] += a[i]
    # Обновляем количество программ для следующего числа командой +1
    a[i + 1] += a[i]

# Количество программ, приводящих к числу 30 и проходящих через 10
print(a[30])

Решение рекурсией

Решение через рекурсию заключается в том, чтобы подсчитать количество программ, которые преобразуют число в число . Для этого определяем функцию f(x, y), которая возвращает количество таких программ.

1. Если текущее число совпало с числом , значит найден корректный путь, функция возвращает 1.

2. Если текущее число меньше числа , дальнейшие команды не приведут к , функция возвращает 0.

3. В остальных случаях выполняем рекурсивный подсчет: сумма количества программ при применении каждой из команд. Первая команда уменьшает число на 1, вторая — на 3, третья — берет целую часть от деления на 3. Таким образом, сумма трёх рекурсивных вызовов даст общее количество программ, ведущих из в .

Поскольку траектория должна содержать число 14, общее количество программ, которые из числа 38 приводят к числу 1 через число 14, вычисляется как произведение f(38, 14) * f(14, 1). Первый множитель считает количество программ от 38 до 14, второй — от 14 до 1. Произведение учитывает, что для каждого пути из первой части можно выбрать любой путь из второй части.

# Определяем функцию f(x, y) для подсчета количества программ
def f(x, y):
    # Если текущее число совпало с целевым числом y,
    # значит найден подходящий путь, возвращаем 1
    if x == y:
        return 1
    # Если текущее число стало меньше целевого числа y,
    # дальнейшие команды не смогут привести к y, возвращаем 0
    if x < y:
        return 0
    else:
        # В остальных случаях считаем все возможные переходы:
        # 1) вычесть 1
        # 2) вычесть 3
        # 3) взять целую часть от деления на 3
        # и суммируем количество таких программ
        return f(x - 1, y) + f(x - 3, y) + f(x // 3, y)

# Вычисляем общее количество программ от 38 до 1 через 14
print(f(38, 14) * f(14, 1))

Решение рекурсией

Мы будем использовать рекурсивный подход, создавая функцию f(x, y), которая считает количество способов из числа получить число . При реализации функции мы рассматриваем следующие ситуации:

- Если текущее число совпало с целевым , значит мы нашли один корректный путь, и функция возвращает 1.

- Если текущее число стало меньше , значит достигнут тупик — дальнейшие преобразования не ведут к результату, возвращаем 0.

- В остальных случаях мы рассматриваем все возможные действия:

   - Вычесть 5: вызываем f(x - 5, y)

   - Вычесть 2: вызываем f(x - 2, y)

   - Разделить на 5: вызываем f(x // 5, y), но только если делится на 5 без остатка

Таким образом, на каждом шаге мы суммируем количество программ для всех допустимых действий. Чтобы учесть условие, что траектория должна содержать число 13, мы разбиваем вычисления на два этапа: сначала считаем количество программ от 49 до 13, затем от 13 до 1, и перемножаем результаты, так как любой путь первой части можно соединить с любым путем второй части.

# Определяем функцию f(x, y), которая считает количество программ
def f(x, y):
    # Если текущее число равно целевому, найден один путь
    if x == y:
        return 1
    # Если текущее число стало меньше целевого, путь невозможен
    if x < y:
        return 0
    # Если число кратно 5, учитываем все три команды
    if x % 5 == 0:
        # Суммируем количество программ для всех действий
        return f(x - 5, y) + f(x - 2, y) + f(x // 5, y)
    else:
        # Иначе можем использовать только вычитание 5 и 2
        return f(x - 5, y) + f(x - 2, y)

# Считаем количество программ от 49 до 13 и от 13 до 1, затем перемножаем
print(f(49, 13) * f(13, 1))