23.05 Количество программ из A в B смешанное

Рекурсия:

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

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

Так как нужно, чтобы траектория содержала число 14, но не содержала число 26, то общее количество программ равно произведению f(2, 14) и f(14, 34). Первая часть считает количество способов дойти от 2 до 14, вторая — от 14 до 34, произведение этих значений дает ответ, так как для каждого пути из первой части можно использовать любой путь из второй части.

# Функция для подсчета количества программ преобразования a -> b
def f(a, b):
# Если число больше целевого или равно запрещённому 26,
    # то есть нарушено условие задачи
    if a > b or a == 26:
        return 0
    # Если дошли до целевого числа,
    # то есть получили подходящую траекторию
    if a == b:
        return 1
    # В остальных случаяй, считаем все возможные переходы
    return f(a + 2, b) + f(a + 6, b) + f(a * 2, b)
# Вычисляем и выводим ответ, учитывая условие
# траектория проходит через 14
print(f(2, 14) * f(14, 34))

 

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

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

Для реализации этого способа в программе создадим список, изначально заполненный нулями. Каждое число в списке будет обозначать количество траекторий до определенного числа. Далее пройдем по списку и заполним его значениями. Значение для каждой i-ой ячейки равно сумме значений для ячеек с индексами i-2 (команда Прибавить 2), i-6 (команда Прибавить 6) и i//2 (команда Умножить на 2, только для четных чисел).

По условию траектория не должна содержать число 26, поэтому при подсчете количества траекторий значение в ячейке с индексом 26 должно остаться 0. Также по условию траектория должна содержать число 14. Для этого разделим вычисления на два независимых этапа: из 2 в 14, из 14 в 34. Результаты этих этапов необходимо перемножить, чтобы получить итоговый ответ, так как для каждого пути из первой части можно использовать любой путь из второй части.

# Первый этап: от 2 до 14
# Создаем массив для хранения количества путей до чисел от 0 до 14
# a[i] - количество программ, которые преобразуют число 2 в число i
a = [0] * (14 + 1)
a[2] = 1  # Исходное положение - только один способ быть в числе 2

# Перебираем все числа от 3 до 14 включительно
for i in range(3, 14 + 1):
    # Можно прийти командами Прибавить 2 и Прибавить 6
    ways = a[i-2] + a[i-6]

    # Можно прийти командой Умножить на 2 (только для четных чисел)
    if i % 2 == 0:
        ways += a[i // 2]

    a[i] = ways

# Второй этап: от 14 до 34 (с обязательным исключением числа 26)
# Массив для чисел от 0 до 34
# b[i] - количество программ, которые преобразуют число 14 в число i
b = [0] * (34 + 1)
b[14] = 1  # Начинаем из числа 14, которое должно быть в траектории

# Перебираем все числа от 15 до 34 включительно
for i in range(15, 34 + 1):
    if i == 26:
        continue  # Пропускаем число 26 согласно условию задачи

    # Можно прийти командами Прибавить 2 и Прибавить 6
    ways = b[i-2] + b[i-6]

    # Можно прийти командой Умножить на 2 (только для четных чисел)
    if i % 2 == 0:
        ways += b[i // 2]

    b[i] = ways

# Общее количество программ равно произведению путей до 14 и от 14 до 34
                                                                                                     
                                                                                                     
print(a[14] * b[34])

Рекурсия:

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

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

Так как нужно, чтобы траектория содержала число 50, но не содержала чисел 25 и 40, то общее количество программ равно произведению f(15, 50) и f(50, 100). Первая часть считает количество способов дойти от 14 до 50, вторая — от 50 до 100, произведение этих значений дает ответ, так как для каждого пути из первой части можно использовать любой путь из второй части.

# Функция для подсчета количества программ преобразования a -> b
def f(a,b):
# Если число больше целевого или равно запрещённым 25 или 40,
    # то есть нарушено условие задачи
    if a > b or a == 25 or a == 40 :
     return 0
    # Если дошли до целевого числа,
    # то есть получили подходящую траекторию
    if a == b:
     return 1
    # В остальных случаяй, считаем все возможные переходы
    return f(a + 5, b) + f(a + 10, b) + f(a * 2, b)
# Вычисляем и выводим ответ, учитывая условие
# траектория проходит через 50
print(f(15, 50) * f(50, 100))

 

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

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

Для реализации этого способа в программе создадим список, изначально заполненный нулями. Каждое число в списке будет обозначать количество траекторий до определенного числа. Далее пройдем по списку и заполним его значениями. Значение для каждой i-ой ячейки равно сумме значений для ячеек с индексами i-5 (вариант 1), i-10 (вариант 2) и i//2 (вариант 3, только для четных чисел).

По условию траектория не должна содержать числа 25 и 40, поэтому при подсчете количества траекторий значения в ячейках с индексами 25 и 40 должны остаться 0. Также по условию траектория должна содержать число 50. Для этого разделим вычисления на два независимых этапа: из 15 в 50, из 50 в 100. Результаты этих этапов необходимо перемножить, чтобы получить итоговый ответ, так как для каждого пути из первой части можно использовать любой путь из второй части.

# Первый этап: от 15 до 50 (с обязательным исключением чисел 25 и 40)
# Создаем массив для хранения количества путей до чисел от 0 до 50
# a[i] - количество программ, которые преобразуют число 15 в число i
a = [0] * (50 + 1)
a[15] = 1  # Исходное положение - только один способ быть в числе 15

# Перебираем все числа от 16 до 50 включительно
for i in range(16, 50 + 1):
    if i == 25 or i == 40:
        continue  # Пропускаем числа 25 и 40 согласно условию задачи

    # Можно прийти командами Прибавить 5 и Прибавить 10
    ways = a[i-5] + a[i-10]

    # Можно прийти командой Умножить на 2 (только для четных чисел)
    if i % 2 == 0:
        ways += a[i // 2]

    a[i] = ways

# Второй этап: от 50 до 100
# Массив для чисел от 0 до 100
# b[i] - количество программ, которые преобразуют число 50 в число i
b = [0] * (100 + 1)
b[50] = 1  # Начинаем из числа 50, которое должно быть в траектории

# Перебираем все числа от 51 до 100 включительно
for i in range(51, 100 + 1):
    # Можно прийти командами Прибавить 5 и Прибавить 10
    ways = b[i-5] + b[i-10]

    # Можно прийти командой Умножить на 2 (только для четных чисел)
    if i % 2 == 0:
        ways += b[i // 2]

    b[i] = ways

# Общее количество программ равно произведению путей до 50 и от 50 до 100
print(a[50] * b[100])

Рекурсия:

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

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

Так как нужно, чтобы траектория содержала число 18, но не содержала число 39, то общее количество программ равно произведению f(2, 18) и f(18, 61). Первая часть считает количество способов дойти от 2 до 18, вторая — от 18 до 61, произведение этих значений дает ответ, так как для каждого пути из первой части можно использовать любой путь из второй части.

# Функция для подсчета количества программ преобразования a -> b
def f(a, b):
# Если число больше целевого или равно запрещённому 39,
    # то есть нарушено условие задачи
    if a > b or a == 39:
        return 0
    # Если дошли до целевого числа,
    # то есть получили подходящую траекторию
    if a == b:
        return 1
    # В остальных случаяй, считаем все возможные переходы
    return f(a + 1, b) + f(a + 10, b) + f(a * 2, b)
# Вычисляем и выводим ответ, учитывая условие
# траектория проходит через 18
print(f(2, 18) * f(18, 61))

 

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

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

Для реализации этого способа в программе создадим список, изначально заполненный нулями. Каждое число в списке будет обозначать количество траекторий до определенного числа. Далее пройдем по списку и заполним его значениями. Значение для каждой i-ой ячейки равно сумме значений для ячеек с индексами i-1 (команда Прибавить 1), i-10 (команда Прибавить 10) и i//2 (команда Умножить на 2, только для четных чисел).

По условию траектория не должна содержать число 39, поэтому при подсчете количества траекторий значение в ячейке с индексом 39 должно остаться 0. Также по условию траектория должна содержать число 18. Для этого разделим вычисления на два независимых этапа: из 2 в 18, из 18 в 61. Результаты этих этапов необходимо перемножить, чтобы получить итоговый ответ, так как для каждого пути из первой части можно использовать любой путь из второй части.

# Первый этап: от 2 до 18
# Создаем массив для хранения количества путей до чисел от 0 до 18
# a[i] - количество программ, которые преобразуют число 2 в число i
a = [0] * (18 + 1)
a[2] = 1  # Исходное положение - только один способ быть в числе 2

# Перебираем все числа от 3 до 18 включительно
for i in range(3, 18 + 1):
    # Можно прийти командой Прибавить 1
    ways = a[i-1]

    # Можно прийти командой Прибавить 10 (если i-10 >= 2)
    if i-10 >= 2:
        ways += a[i-10]

    # Можно прийти командой Умножить на 2 (только для четных чисел)
    if i % 2 == 0:
        ways += a[i // 2]

    a[i] = ways

# Второй этап: от 18 до 61
# Массив для чисел от 0 до 61 (с обязательным исключением числа 39)
# b[i] - количество программ, которые преобразуют число 18 в число i
b = [0] * (61 + 1)
b[18] = 1  # Начинаем из числа 18, которое должно быть в траектории

# Перебираем все числа от 19 до 61 включительно
for i in range(19, 61 + 1):
    if i == 39:
        continue  # Пропускаем число 39 согласно условию задачи

    # Можно прийти командой Прибавить 1
    ways = b[i-1]

    # Можно прийти командой Прибавить 10 (если i-10 >= 18)
    if i-10 >= 18:
        ways += b[i-10]
                                                                                                     
                                                                                                     

    # Можно прийти командой Умножить на 2 (только для четных чисел)
    if i % 2 == 0:
        ways += b[i // 2]

    b[i] = ways

# Общее количество программ равно произведению путей до 18 и от 18 до 61
print(a[18] * b[61])

Рекурсия:

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

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

Так как нужно, чтобы траектория содержала число 13, но не содержала число 29, то общее количество программ равно произведению f(4, 13) и f(13, 49). Первая часть считает количество способов дойти от 4 до 13, вторая — от 13 до 49, произведение этих значений дает ответ, так как для каждого пути из первой части можно использовать любой путь из второй части.

# Функция для подсчета количества программ преобразования a -> b
def f(a, b):
# Если число больше целевого или равно запрещённому 29,
    # то есть нарушено условие задачи
    if a > b or a == 29:
        return 0
    # Если дошли до целевого числа,
    # то есть получили подходящую траекторию
    if a == b:
        return 1
    # В остальных случаяй, считаем все возможные переходы
    return f(a + 1, b) + f(a + 9, b)
# Вычисляем и выводим ответ, учитывая условие
# траектория проходит через 13
print(f(4, 13) * f(13, 49))

 

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

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

Для реализации этого способа в программе создадим список, изначально заполненный нулями. Каждое число в списке будет обозначать количество траекторий до определенного числа. Далее пройдем по списку и заполним его значениями. Значение для каждой i-ой ячейки равно сумме значений для ячеек с индексами i-1 (команда Прибавить 1) и i-9 (команда Прибавить 9).

По условию траектория не должна содержать число 29, поэтому при подсчете количества траекторий значение в ячейке с индексом 29 должно остаться 0. Также по условию траектория должна содержать число 13. Для этого разделим вычисления на два независимых этапа: из 4 в 13, из 13 в 49. Результаты этих этапов необходимо перемножить, чтобы получить итоговый ответ, так как для каждого пути из первой части можно использовать любой путь из второй части.

# Первый этап: от 4 до 13
# Создаем массив для хранения количества путей до чисел от 0 до 13
# a[i] - количество программ, которые преобразуют число 4 в число i
a = [0] * (13 + 1)
a[4] = 1  # Исходное положение - только один способ быть в числе 4

# Перебираем все числа от 5 до 13 включительно
for i in range(5, 13 + 1):
    # Можно прийти командой Прибавить 1
    ways = a[i-1]

    # Можно прийти командой Прибавить 9 (если i-9 >= 4)
    if i-9 >= 4:
        ways += a[i-9]

    a[i] = ways

# Второй этап: от 13 до 49
# Массив для чисел от 0 до 49 (с обязательным исключением числа 29)
# b[i] - количество программ, которые преобразуют число 13 в число i
b = [0] * (49 + 1)
b[13] = 1  # Начинаем из числа 13, которое должно быть в траектории

# Перебираем все числа от 14 до 49 включительно
for i in range(14, 49 + 1):
    if i == 29:
        continue  # Пропускаем число 29 согласно условию задачи

    # Можно прийти командой Прибавить 1
    ways = b[i-1]

    # Можно прийти командой Прибавить 9 (если i-9 >= 13)
    if i-9 >= 13:
        ways += b[i-9]

    b[i] = ways

# Общее количество программ равно произведению путей до 13 и от 13 до 49
                                                                                                     
                                                                                                     
print(a[13] * b[49])

Рекурсия:

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

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

Так как нужно, чтобы траектория содержала число 11, но не содержала число 14, то общее количество программ равно произведению f(3, 11) и f(11, 24). Первая часть считает количество способов дойти от 3 до 11, вторая — от 11 до 24, произведение этих значений дает ответ, так как для каждого пути из первой части можно использовать любой путь из второй части.

# Функция для подсчета количества программ преобразования a -> b
def f(a, b):
# Если число больше целевого или равно запрещённому 14,
    # то есть нарушено условие задачи
    if a > b or a == 14:
        return 0
    # Если дошли до целевого числа,
    # то есть получили подходящую траекторию
    if a == b:
        return 1
    # В остальных случаяй, считаем все возможные переходы
    return f(a + 1, b) + f(a + 2, b)
# Вычисляем и выводим ответ, учитывая условие
# траектория проходит через 11
print(f(3, 11) * f(11, 24))

 

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

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

Для реализации этого способа в программе создадим список, изначально заполненный нулями. Каждое число в списке будет обозначать количество траекторий до определенного числа. Далее пройдем по списку и заполним его значениями. Значение для каждой i-ой ячейки равно сумме значений для ячеек с индексами i-1 (команда Прибавить 1) и i-2 (команда Прибавить 2).

По условию траектория не должна содержать число 14, поэтому при подсчете количества траекторий значение в ячейке с индексом 14 должно остаться 0. Также по условию траектория должна содержать число 11. Для этого разделим вычисления на два независимых этапа: из 3 в 11, из 11 в 24. Результаты этих этапов необходимо перемножить, чтобы получить итоговый ответ, так как для каждого пути из первой части можно использовать любой путь из второй части.

# Первый этап: от 3 до 11
# Создаем массив для хранения количества путей до чисел от 0 до 11
# a[i] - количество программ, которые преобразуют число 3 в число i
a = [0] * (11 + 1)
a[3] = 1  # Исходное положение - только один способ быть в числе 3

# Перебираем все числа от 4 до 11 включительно
for i in range(4, 11 + 1):
    # Можно прийти командой Прибавить 1 и командой Прибавить 2
    a[i] = a[i-1] + a[i-2]

# Второй этап: от 11 до 24
# Массив для чисел от 0 до 24 (с обязательным исключением числа 14)
# b[i] - количество программ, которые преобразуют число 11 в число i
b = [0] * (24 + 1)
b[11] = 1  # Начинаем из числа 11, которое должно быть в траектории

# Перебираем все числа от 12 до 24 включительно
for i in range(12, 24 + 1):
    if i == 14:
        continue  # Пропускаем число 14 согласно условию задачи

    # Можно прийти командой Прибавить 1 и командой Прибавить 2
    b[i] = b[i-1] + b[i-2]

# Общее количество программ равно произведению путей до 11 и от 11 до 24
print(a[11] * b[24])

Рекурсия:

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

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

Так как нужно, чтобы траектория содержала числа 11 и 21, но не содержала число 15, то общее количество программ равно произведению f(3, 11), f(11, 21) и f(21, 45). Первая часть считает количество способов дойти от 3 до 11, вторая — от 11 до 21, третья - от 21 до 45 произведение этих значений дает ответ, так как для каждого пути из первой части можно использовать любой путь из второй части и кажому пути из второй части можно подобрать путь из третьей.

# Функция для подсчета количества программ преобразования a -> b
def f(a, b):
# Если число больше целевого или равно запрещённому 15,
    # то есть нарушено условие задачи
    if a > b or a == 15:
        return 0
    # Если дошли до целевого числа,
    # то есть получили подходящую траекторию
    if a == b:
        return 1
    # В остальных случаяй, считаем все возможные переходы
    return f(a + 2, b) + f(a * 5, b)
# Вычисляем и выводим ответ, учитывая условие
# траектория проходит через 11 и 21
print(f(3, 11) * f(11, 21) * f(21, 45))

 

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

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

Для реализации этого способа в программе создадим список, изначально заполненный нулями. Каждое число в списке будет обозначать количество траекторий до определенного числа. Далее пройдем по списку и заполним его значениями. Значение для каждой i-ой ячейки равно сумме значений для ячеек с индексами i-2 (команда Прибавить 2) и i//5 (команда Умножить на 5, только для чисел кратных 5).

По условию траектория не должна содержать число 15, поэтому при подсчете количества траекторий значение в ячейке с индексом 15 должно остаться 0. Также по условию траектория должна содержать числа 11 и 21. Для этого разделим вычисления на три независимых этапа: из 3 в 11, из 11 в 21, из 21 в 45. Результаты этих этапов необходимо перемножить, чтобы получить итоговый ответ, так как для каждого пути из каждой части можно использовать любой путь из следующих частей.

# Первый этап: от 3 до 11
# Создаем массив для хранения количества путей до чисел от 0 до 11
# a[i] - количество программ, которые преобразуют число 3 в число i
a = [0] * (11 + 1)
a[3] = 1  # Исходное положение - только один способ быть в числе 3

# Перебираем все числа от 4 до 11 включительно
for i in range(4, 11 + 1):
    # Можно прийти командой Прибавить 2
    ways = a[i-2]

    # Можно прийти командой Умножить на 5 (только для чисел кратных 5)
    if i % 5 == 0:
        ways += a[i // 5]

    a[i] = ways

# Второй этап: от 11 до 21
# Массив для чисел от 0 до 21 (с обязательным исключением числа 15)
# b[i] - количество программ, которые преобразуют число 11 в число i
b = [0] * (21 + 1)
b[11] = 1  # Начинаем из числа 11, которое должно быть в траектории

# Перебираем все числа от 12 до 21 включительно
for i in range(12, 21 + 1):
    if i == 15:
        continue  # Пропускаем число 15 согласно условию задачи

    # Можно прийти командой Прибавить 2
    ways = b[i-2]

    # Можно прийти командой Умножить на 5 (только для чисел кратных 5)
    if i % 5 == 0:
        ways += b[i // 5]

    b[i] = ways

# Третий этап: от 21 до 45
                                                                                                     
                                                                                                     
# Массив для чисел от 0 до 45
# c[i] - количество программ, которые преобразуют число 21 в число i
c = [0] * (45 + 1)
c[21] = 1  # Начинаем из числа 21, которое должно быть в траектории

# Перебираем все числа от 22 до 45 включительно
for i in range(22, 45 + 1):
    # Можно прийти командой Прибавить 2
    ways = c[i-2]

    # Можно прийти командой Умножить на 5 (только для чисел кратных 5)
    if i % 5 == 0:
        ways += c[i // 5]

    c[i] = ways

# Общее количество программ равно произведению путей всех трех этапов
print(a[11] * b[21] * c[45])

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

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

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

Так как нужно, чтобы траектория содержала число 17, но не содержала число 21, то общее количество программ равно произведению f(5, 17) и f(17, 37). Первая часть считает количество способов дойти от 5 до 17, вторая — от 17 до 37, произведение этих значений дает ответ, так как для каждого пути из первой части можно использовать любой путь из второй части.

# Функция для подсчета количества программ преобразования a -> b
def f(a, b):
# Если число больше целевого или равно запрещённому 21,
    # то есть нарушено условие задачи
    if a > b or a == 21:
        return 0
    # Если дошли до целевого числа,
    # то есть получили подходящую траекторию
    if a == b:
        return 1
    # В остальных случаяй, считаем все возможные переходы
    return f(a+2, b) + f(a*3, b) + f(a*2-1, b)
# Вычисляем и выводим ответ, учитывая условие
# траектория проходит через 17
print(f(5, 17) * f(17, 37))

Рекурсия:

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

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

Так как нужно, чтобы траектория содержала число 21, но не содержала число 31, то общее количество программ равно произведению f(1, 21) и f(21, 66). Первая часть считает количество способов дойти от 1 до 21, вторая — от 21 до 66, произведение этих значений дает ответ, так как для каждого пути из первой части можно использовать любой путь из второй части.

# Функция для подсчета количества программ преобразования a -> b
def f(a, b):
# Если число больше целевого или равно запрещённому 31,
    # то есть нарушено условие задачи
    if a > b or a == 31:
        return 0
    # Если дошли до целевого числа,
    # то есть получили подходящую траекторию
    if a == b:
        return 1
    # В остальных случаяй, считаем все возможные переходы
    return f(a + 1, b) + f(a + 5, b)
# Вычисляем и выводим ответ, учитывая условие
# траектория проходит через 21
print(f(1, 21) * f(21, 66))

 

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

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

Для реализации этого способа в программе создадим список, изначально заполненный нулями. Каждое число в списке будет обозначать количество траекторий до определенного числа. Далее пройдем по списку и заполним его значениями. Значение для каждой i-ой ячейки равно сумме значений для ячеек с индексами i-1 (команда Прибавить 1) и i-5 (команда Прибавить 5).

По условию траектория не должна содержать число 31, поэтому при подсчете количества траекторий значение в ячейке с индексом 31 должно остаться 0. Также по условию траектория должна содержать число 21. Для этого разделим вычисления на два независимых этапа: из 1 в 21, из 21 в 66. Результаты этих этапов необходимо перемножить, чтобы получить итоговый ответ, так как для каждого пути из первой части можно использовать любой путь из второй части.

# Первый этап: от 1 до 21
# Создаем массив для хранения количества путей до чисел от 0 до 21
# a[i] - количество программ, которые преобразуют число 1 в число i
a = [0] * (21 + 1)
a[1] = 1  # Исходное положение - только один способ быть в числе 1

# Перебираем все числа от 2 до 21 включительно
for i in range(2, 21 + 1):
    # Можно прийти командой Прибавить 1
    ways = a[i-1]

    # Можно прийти командой Прибавить 5 (если i-5 >= 1)
    if i-5 >= 1:
        ways += a[i-5]

    a[i] = ways

# Второй этап: от 21 до 66
# Массив для чисел от 0 до 66 (с обязательным исключением числа 31)
# b[i] - количество программ, которые преобразуют число 21 в число i
b = [0] * (66 + 1)
b[21] = 1  # Начинаем из числа 21, которое должно быть в траектории

# Перебираем все числа от 22 до 66 включительно
for i in range(22, 66 + 1):
    if i == 31:
        continue  # Пропускаем число 31 согласно условию задачи

    # Можно прийти командой Прибавить 1
    ways = b[i-1]

    # Можно прийти командой Прибавить 5 (если i-5 >= 21)
    if i-5 >= 21:
        ways += b[i-5]

    b[i] = ways

# Общее количество программ равно произведению путей до 21 и от 21 до 66
print(a[21] * b[66])

Рекурсия:

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

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

Так как нужно, чтобы траектория содержала число 14, но не содержала число 20, то общее количество программ равно произведению f(4, 14) и f(14, 42). Первая часть считает количество способов дойти от 4 до 14, вторая — от 14 до 42, произведение этих значений дает ответ, так как для каждого пути из первой части можно использовать любой путь из второй части.

# Функция для подсчета количества программ преобразования a -> b
def f(a, b):
# Если число больше целевого или равно запрещённому 20,
    # то есть нарушено условие задачи
    if a > b or a == 20:
        return 0
    # Если дошли до целевого числа,
    # то есть получили подходящую траекторию
    if a == b:
        return 1
    # В остальных случаяй, считаем все возможные переходы
    return f(a + 2, b) + f(a + 6, b) + f(a * 3, b)
# Вычисляем и выводим ответ, учитывая условие
# траектория проходит через 14
print(f(4, 14) * f(14, 42))

 

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

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

Для реализации этого способа в программе создадим список, изначально заполненный нулями. Каждое число в списке будет обозначать количество траекторий до определенного числа. Далее пройдем по списку и заполним его значениями. Значение для каждой i-ой ячейки равно сумме значений для ячеек с индексами i-2 (команда Прибавить 2), i-6 (команда Прибавить 6) и i//3 (команда Умножить на 3, только для чисел кратных 3).

По условию траектория не должна содержать число 20, поэтому при подсчете количества траекторий значение в ячейке с индексом 20 должно остаться 0. Также по условию траектория должна содержать число 14. Для этого разделим вычисления на два независимых этапа: из 4 в 14, из 14 в 42. Результаты этих этапов необходимо перемножить, чтобы получить итоговый ответ, так как для каждого пути из первой части можно использовать любой путь из второй части.

# Первый этап: от 4 до 14
# Создаем массив для хранения количества путей до чисел от 0 до 14
# a[i] - количество программ, которые преобразуют число 4 в число i
a = [0] * (14 + 1)
a[4] = 1  # Исходное положение - только один способ быть в числе 4

# Перебираем все числа от 5 до 14 включительно
for i in range(5, 14 + 1):
    # Можно прийти командой Прибавить 2
    ways = a[i-2]

    # Можно прийти командой Прибавить 6 (если i-6 >= 0)
    if i-6 >= 0:
        ways += a[i-6]

    # Можно прийти командой Умножить на 3 (только для чисел кратных 3)
    if i % 3 == 0:
        ways += a[i // 3]

    a[i] = ways

# Второй этап: от 14 до 42 (с обязательным исключением числа 20)
# Массив для чисел от 0 до 42
# b[i] - количество программ, которые преобразуют число 14 в число i
b = [0] * (42 + 1)
b[14] = 1  # Начинаем из числа 14, которое должно быть в траектории

# Перебираем все числа от 15 до 42 включительно
for i in range(15, 42 + 1):
    if i == 20:
        continue  # Пропускаем число 20 согласно условию задачи

    # Можно прийти командой Прибавить 2
    ways = b[i-2]

    # Можно прийти командой Прибавить 6
    ways += b[i-6]

    # Можно прийти командой Умножить на 3 (только для чисел кратных 3)
    if i % 3 == 0:
        ways += b[i // 3]
    b[i] = ways
                                                                                                  
                                                                                                  

# Общее количество программ равно произведению путей до 14 и от 14 до 42
print(a[14] * b[42])

Рекурсия:

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

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

Так как нужно, чтобы траектория содержала число 28, но не содержала число 19, то общее количество программ равно произведению f(3, 28) и f(28,35). Первая часть считает количество способов дойти от 3 до 28, вторая — от 28 до 35, произведение этих значений дает ответ, так как для каждого пути из первой части можно использовать любой путь из второй части.

# Функция для подсчета количества программ преобразования a -> b
def f(a, b):
# Если число больше целевого или равно запрещённому 19,
    # то есть нарушено условие задачи
    if a > b or a == 19:
        return 0
    # Если дошли до целевого числа,
    # то есть получили подходящую траекторию
    if a == b:
        return 1
    # В остальных случаяй, считаем все возможные переходы
    return f(a+2, b) + f(a*2, b) + f(a*3, b)
# Вычисляем и выводим ответ, учитывая условие
# траектория проходит через 28
print(f(3, 28) * f(28, 35))

 

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

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

Для реализации этого способа в программе создадим список, изначально заполненный нулями. Каждое число в списке будет обозначать количество траекторий до определенного числа. Далее пройдем по списку и заполним его значениями. Значение для каждой i-ой ячейки равно сумме значений для ячеек с индексами i-2 (команда Прибавить 2), i//2 (команда Умножить на 2, только для четных чисел) и i//3 (команда Умножить на 3, только для чисел кратных 3).

По условию траектория не должна содержать число 19, поэтому при подсчете количества траекторий значение в ячейке с индексом 19 должно остаться 0. Также по условию траектория должна содержать число 28. Для этого разделим вычисления на два независимых этапа: из 3 в 28, из 28 в 35. Результаты этих этапов необходимо перемножить, чтобы получить итоговый ответ, так как для каждого пути из первой части можно использовать любой путь из второй части.

# Первый этап: от 3 до 28 (с обязательным исключением числа 19)
# Создаем массив для хранения количества путей до чисел от 0 до 28
# a[i] - количество программ, которые преобразуют число 3 в число i
a = [0] * (28 + 1)
a[3] = 1  # Исходное положение - только один способ быть в числе 3

# Перебираем все числа от 4 до 28 включительно
for i in range(4, 28 + 1):
    if i == 19:
        continue  # Пропускаем число 19 согласно условию задачи

    # Всегда можно прийти командой Прибавить 2
    ways = a[i-2]

    # Можно прийти командой Умножить на 2 (только для четных чисел)
    if i % 2 == 0:
        ways += a[i // 2]

    # Можно прийти командой Умножить на 3 (только для чисел кратных 3)
    if i % 3 == 0:
        ways += a[i // 3]

    a[i] = ways

# Второй этап: от 28 до 35
# Массив для чисел от 0 до 35
# b[i] - количество программ, которые преобразуют число 28 в число i
b = [0] * (35 + 1)
b[28] = 1  # Начинаем из числа 28, которое должно быть в траектории

# Перебираем все числа от 29 до 35 включительно
for i in range(29, 35 + 1):
    # Всегда можно прийти командой Прибавить 2
    ways = b[i-2]

    # Можно прийти командой Умножить на 2 (только для четных чисел)
    if i % 2 == 0:
        ways += b[i // 2]

    # Можно прийти командой Умножить на 3 (только для чисел кратных 3)
    if i % 3 == 0:
        ways += b[i // 3]
                                                                                                  
                                                                                                  

    b[i] = ways

# Общее количество программ равно произведению путей до 28 и от 28 до 35
print(a[28] * b[35])

Рекурсия:

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

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

Так как нужно, чтобы траектория содержала число 16, но не содержала число 40, то общее количество программ равно произведению f(1, 16) и f(16, 60). Первая часть считает количество способов дойти от 1 до 16, вторая — от 16 до 60, произведение этих значений дает ответ, так как для каждого пути из первой части можно использовать любой путь из второй части.

# Функция для подсчета количества программ преобразования a -> b
def f(a,b):
# Если число больше целевого или равно запрещённому 40,
    # то есть нарушено условие задачи
    if a > b  or a == 40:
        return 0
    # Если дошли до целевого числа,
    # то есть получили подходящую траекторию
    if a == b:
        return 1
    # В остальных случаяй, считаем все возможные переходы
    return f(a + 1, b) + f(a * 3, b)
# Вычисляем и выводим ответ, учитывая условие
# траектория проходит через 16
print(f(1, 16) * f(16, 60))

 

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

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

Для реализации этого способа в программе создадим список, изначально заполненный нулями. Каждое число в списке будет обозначать количество траекторий до определенного числа. Далее пройдем по списку и заполним его значениями. Значение для каждой i-ой ячейки равно сумме значений для ячеек с индексами i-1 и i//3 (только для чисел, кратных 3).

По условию траектория не должна содержать число 40, поэтому при подсчете количества траекторий значение в ячейке с индексом 40 должно остаться 0. Также по условию траектория должна содержать число 16. Для этого разделим вычисления на два независимых этапа: из 1 в 16, из 16 в 60. Результаты этих этапов необходимо перемножить, чтобы получить итоговый ответ, так как для каждого пути из первой части можно использовать любой путь из второй части.

# Первый этап: от 1 до 16
# Создаем массив для хранения количества путей до чисел от 0 до 16
# a[i] - количество программ, которые преобразуют число 1 в число i
a = [0] * (16 + 1)
a[1] = 1  # Исходное положение - только один способ быть в числе 1

# Перебираем все числа от 2 до 16 включительно
for i in range(2, 16 + 1):

    # Для всех чисел учитываем команду +1
    ways = a[i - 1]

    # Для чисел, кратных 3, добавляем команду *3
    if i % 3 == 0:
        ways += a[i // 3]

    a[i] = ways

# Второй этап: от 16 до 60 (с обязательным исключением числа 40)
# Массив для чисел от 0 до 60
# b[i] - количество программ, которые преобразуют число 16 в число i
b = [0] * (60 + 1)
b[16] = 1  # Начинаем из числа 16, которое должно быть в траектории

# Перебираем все числа от 17 до 60 включительно
for i in range(17, 60 + 1):
    if i == 40:
        continue  # Пропускаем запрещенное число согласно условию задачи

    # Для всех чисел учитываем команду +1
    ways = b[i - 1]

    # Для чисел, кратных 3, добавляем команду *3
    if i % 3 == 0:
        ways += b[i // 3]

    b[i] = ways

# Общее количество программ равно произведению путей до 16 и от 16 до 60
print(a[16] * b[60])

Рекурсия:

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

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

Так как нужно, чтобы траектория содержала число 15, но не содержала чисел 10 и 20, то общее количество программ равно произведению f(3, 15) и f(15, 30). Первая часть считает количество способов дойти от 3 до 15, вторая — от 15 до 30, произведение этих значений дает ответ, так как для каждого пути из первой части можно использовать любой путь из второй части.

# Функция для подсчета количества программ преобразования a -> b
def f(a, b):
    # Если число больше целевого или равно запрещённым 10 и 20,
    # то есть нарушено условие задачи
    if a > b or a == 10 or a == 20:
        return 0
    # Если дошли до целевого числа,
    # то есть получили подходящую траекторию
    if a == b:
        return 1
    # В остальных случаяй, считаем все возможные переходы
    return f(a + 1, b) + f(a * 3, b) + f(a + 2, b)
# Вычисляем и выводим ответ, учитывая условие
# траектория проходит через 15
print(f(3, 15) * f(15, 30))

 

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

Динамический способ решения заключается в подсчете количества траекторий для каждого числа, опираясь на подсчеты для предыдущих значений. Для подсчета количества траекторий до числа 30 необходимо знать количество траекторий до чисел 29, 28 и 10 (для команды умножения на 3).

Для реализации этого способа в программе создадим список, изначально заполненный нулями. Каждое число в списке будет обозначать количество траекторий до определенного числа. Далее пройдем по списку и заполним его значениями. Значение для каждой i-ой ячейки равно сумме значений для ячеек с индексами i-1, i-2 и i//3 (только для чисел, кратных 3).

По условию траектория не должна содержать числа 10 и 20, поэтому при подсчете количества траекторий значения в ячейках с индексами 10 и 20 должны остаться 0. Также по условию траектория должна содержать число 15. Для этого разделим вычисления на два независимых этапа: из 3 в 15, из 15 в 30. Результаты этих этапов необходимо перемножить, чтобы получить итоговый ответ, так как для каждого пути из первой части можно использовать любой путь из второй части.

# Первый этап: от 3 до 15 (с обязательным исключением числа 10)
# Создаем массив для хранения количества путей до чисел от 0 до 15
# a[i] - количество программ, которые преобразуют число 3 в число i
a = [0] * (15 + 1)
a[3] = 1  # Исходное положение - только один способ быть в числе 3

# Перебираем все числа от 4 до 15 включительно
for i in range(4, 15 + 1):
    if i == 10:
        continue  # Пропускаем запрещенные числа согласно условию задачи

    # Для всех чисел учитываем команды +1 и +2
    ways = a[i - 1] + a[i - 2]

    # Для чисел, кратных 3, добавляем команду *3
    if i % 3 == 0:
        ways += a[i // 3]

    a[i] = ways

# Второй этап: от 15 до 30 (с обязательным исключением числа 20)
# Массив для чисел от 0 до 30
# b[i] - количество программ, которые преобразуют число 15 в число i
b = [0] * (30 + 1)
b[15] = 1  # Начинаем из числа 15, которое должно быть в траектории

# Перебираем все числа от 16 до 30 включительно
for i in range(16, 30 + 1):
    if i == 20:
        continue  # Пропускаем запрещенные числа согласно условию задачи

    # Для всех чисел учитываем команды +1 и +2
    ways = b[i - 1] + b[i - 2]

    # Для чисел, кратных 3, добавляем команду *3
    if i % 3 == 0:
        ways += b[i // 3]

    b[i] = ways

# Общее количество программ равно произведению путей до 15 и от 15 до 30
print(a[15] * b[30])
                                                                                                  
                                                                                                  

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

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

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

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

# Функция для подсчета количества программ преобразования a -> b
def f(a, b):
# Если число больше целевого или равно запрещённому 14,
    # то есть нарушено условие задачи
    if a > b or a == 14:
        return 0
    # Если дошли до целевого числа,
    # то есть получили подходящую траекторию
    if a == b:
        return 1
    # В остальных случаяй, считаем все возможные переходы
    return f(a + 1, b) + f(a + 3, b) + f(a * 2, b)
# Вычисляем и выводим ответ, учитывая условие
# траектория проходит через 9
print(f(1, 9) * f(9, 20))

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

Динамический способ решения заключается в подсчете количества траекторий для каждого числа, опираясь на подсчеты для предыдущих значений. Для подсчета количества траекторий до числа 20 необходимо знать количество траекторий до чисел 19, 10 (для команды умножения на 2) и 17 .

Для реализации этого способа в программе создадим список, изначально заполненный нулями. Каждое число в списке будет обозначать количество траекторий до определенного числа. Далее пройдем по списку и заполним его значениями. Значение для каждой i-ой ячейки равно сумме значений для ячеек с индексами i-1, i//2 (для четных чисел) и i-3.

По условию траектория не должна содержать число 14, поэтому при подсчете количества траекторий значение в ячейке с индексом 14 должно остаться 0. Также по условию траектория должна содержать число 9. Для этого разделим вычисления на два независимых этапа: из 1 в 9, из 9 в 20. Результаты этих этапов необходимо перемножить, чтобы получить итоговый ответ, так как для каждого пути из первой части можно использовать любой путь из второй части.

# Первый этап: от 1 до 9 (с обязательным исключением числа 14)
# Создаем массив для хранения количества путей до чисел от 0 до 9
# a[i] - количество программ, которые преобразуют число 1 в число i
a = [0] * (9 + 1)
a[1] = 1  # Исходное положение - только один способ быть в числе 1

# Перебираем все числа от 2 до 9 включительно
for i in range(2, 9 + 1):
    if i == 14:
        continue  # Пропускаем запрещенное число согласно условию задачи

    # Для всех чисел учитываем команду +1
    ways = a[i - 1]

    # Для четных чисел добавляем команду *2
    if i % 2 == 0:
        ways += a[i // 2]

    # Для чисел >= 4 добавляем команду +3
    if i >= 4:
        ways += a[i - 3]

    a[i] = ways

# Второй этап: от 9 до 20 (также исключаем число 14)
# Массив для чисел от 0 до 20
# b[i] - количество программ, которые преобразуют число 9 в число i
b = [0] * (20 + 1)
b[9] = 1  # Начинаем из числа 9, которое должно быть в траектории

# Перебираем все числа от 10 до 20 включительно
for i in range(10, 20 + 1):
    if i == 14:
        continue  # Пропускаем запрещенное число согласно условию задачи

    # Для всех чисел учитываем команду +1
    ways = b[i - 1]

    # Для четных чисел добавляем команду *2
    if i % 2 == 0:
        ways += b[i // 2]

                                                                                                  
                                                                                                  
    # Для чисел >= 12 добавляем команду +3
    if i >= 12:
        ways += b[i - 3]

    b[i] = ways

# Общее количество программ равно произведению путей до 9 и от 9 до 20
print(a[9] * b[20])

Рекурсия:

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

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

Так как нужно, чтобы траектория содержала число 10, но не содержала чисел 8 и 15, то общее количество программ равно произведению f(3, 10) и f(10, 22). Первая часть считает количество способов дойти от 3 до 10, вторая — от 10 до 22, произведение этих значений дает ответ, так как для каждого пути из первой части можно использовать любой путь из второй части.

# Функция для подсчета количества программ преобразования a -> b
def f(a, b):
    # Если число больше целевого или равно запрещённым 8 или 15,
    # то есть нарушено условие задачи
    if a > b or a == 8 or a == 15:
     return 0
    # Если дошли до целевого числа,
    # то есть получили подходящую траекторию
    if a == b:
     return 1
    # В остальных случаяй, считаем все возможные переходы
    return f(a + 1, b) + f(a + 2, b) + f(a * 3, b)
# Вычисляем и выводим ответ, учитывая условие
# траектория проходит через 10
print(f(3, 10) * f(10, 22))

 

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

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

Для реализации этого способа в программе создадим список, изначально заполненный нулями. Каждое число в списке будет обозначать количество траекторий до определенного числа. Далее пройдем по списку и заполним его значениями. Значение для каждой i-ой ячейки равно сумме значений для ячеек с индексами i-1, i-2 и i//3 (только для чисел, кратных 3).

По условию траектория не должна содержать числа 8 и 15, поэтому при подсчете количества траекторий значения в ячейках с индексами 8 и 15 должны остаться 0. Также по условию траектория должна содержать число 10. Для этого разделим вычисления на два независимых этапа: из 3 в 10, из 10 в 22. Результаты этих этапов необходимо перемножить, чтобы получить итоговый ответ, так как для каждого пути из первой части можно использовать любой путь из второй части.

# Первый этап: от 3 до 10 (с обязательным исключением числа 8)
# Создаем массив для хранения количества путей до чисел от 0 до 10
# a[i] - количество программ, которые преобразуют число 3 в число i
a = [0] * (10 + 1)
a[3] = 1  # Исходное положение - только один способ быть в числе 3

# Перебираем все числа от 4 до 10 включительно
for i in range(4, 10 + 1):
    if i == 8:
        continue  # Пропускаем запрещенные числа согласно условию задачи

    # Для всех чисел учитываем команды +1 и +2
    ways = a[i - 1] + a[i - 2]

    # Для чисел, кратных 3, добавляем команду *3
    if i % 3 == 0:
        ways += a[i // 3]

    a[i] = ways

# Второй этап: от 10 до 22 (с обязательным исключением числа 15)
# Массив для чисел от 0 до 22
# b[i] - количество программ, которые преобразуют число 10 в число i
b = [0] * (22 + 1)
b[10] = 1  # Начинаем из числа 10, которое должно быть в траектории

# Перебираем все числа от 11 до 22 включительно
for i in range(11, 22 + 1):
    if i == 15:
        continue  # Пропускаем запрещенные числа согласно условию задачи

    # Для всех чисел учитываем команды +1 и +2
    ways = b[i - 1] + b[i - 2]

    # Для чисел, кратных 3, добавляем команду *3
    if i % 3 == 0:
        ways += b[i // 3]

    b[i] = ways

# Общее количество программ равно произведению путей до 10 и от 10 до 22
print(a[10] * b[22])
                                                                                                  
                                                                                                  

Рекурсия:

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

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

Так как нужно, чтобы траектория содержала число 18, но не содержала число 12, то общее количество программ равно произведению f(3, 18) и f(18, 55). Первая часть считает количество способов дойти от 3 до 18, вторая — от 18 до 55, произведение этих значений дает ответ, так как для каждого пути из первой части можно использовать любой путь из второй части.

# Функция для подсчета количества программ преобразования a -> b
def f(a, b):
    # Если число больше целевого или равно запрещённому 12,
    # то есть нарушено условие задачи
    if a > b or a == 12:
        return 0
    # Если дошли до целевого числа,
    # то есть получили подходящую траекторию
    if a == b:
        return 1
    # В остальных случаяй, считаем все возможные переходы
    return f(a+1, b) + f(a*2, b)
# Вычисляем и выводим ответ, учитывая условие
# траектория проходит через 18
print(f(3, 18) * f(18, 55))

 

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

Динамический способ решения заключается в подсчете количества траекторий для каждого числа, опираясь на подсчеты для предыдущих значений. Так, например, для подсчета количества траекторий до числа 55 необходимо знать количество траекторий до чисел 54, 53 и 27 (для команды умножения на 2).

Для реализации этого способа в программе создадим список, изначально заполненный нулями. Каждое число в списке будет обозначать количество траекторий до определенного числа. Далее пройдем по списку и заполним его значениями. Значение для каждой i-ой ячейки равно сумме значений для ячеек с индексами i-1 и i//2 (только для четных чисел, так как в нечетные нельзя попасть, используя команду «Умножить на 2»).

По условию траектория не должна содержать число 12, поэтому при подсчете количества траекторий значение в ячейке с индексом 12 должно остаться 0. Также по условию траектория должна содержать число 18. Для этого разделим вычисления на два независимых этапа: из 3 в 18, из 18 в 55. Результаты этих этапов необходимо перемножить, чтобы получить итоговый ответ, так как для каждого пути из первой части можно использовать любой путь из второй части.

# Первый этап: от 3 до 18 (с обязательным исключением числа 12)
# Создаем массив для хранения количества путей до чисел от 0 до 18
# a[i] - количество программ, которые преобразуют число 3 в число i
a = [0] * (18 + 1)
a[3] = 1  # Исходное положение - только один способ быть в числе 3

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

# Второй этап: от 18 до 55 (также исключаем число 12)
# Массив для чисел от 0 до 55
# b[i] - количество программ, которые преобразуют число 18 в число i
b = [0] * (55 + 1)
b[18] = 1  # Начинаем из числа 18, которое должно быть в траектории

# Перебираем все числа от 19 до 55 включительно
for i in range(19, 55 + 1):
    if i == 12:
        continue  # Пропускаем число 12 согласно условию задачи
    if i % 2 == 0:
        # Для четных чисел учитываем обе команды
        b[i] = b[i - 1] + b[i // 2]
    else:
        # Для нечетных чисел - только команду сложения
        b[i] = b[i - 1]

# Общее количество программ равно произведению путей до 18 и от 18 до 55
print(a[18] * b[55])

Рекурсия:

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

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

Так как нужно, чтобы траектория содержала число 24, но не содержала число 22, то общее количество программ равно произведению f(38, 24) и f(24,11). Первая часть считает количество способов дойти от 38 до 24, вторая — от 24 до 11, произведение этих значений дает ответ, так как для каждого пути из первой части можно использовать любой путь из второй части.

# Функция для подсчета количества программ преобразования a -> b
def f(a, b):
    # Если число меньше целевого или равно запрещённому 22,
    # то есть нарушено условие задачи
    if a < b or a == 22:
        return 0
    # Если дошли до целевого числа,
    # то есть получили подходящую траекторию
    if a == b:
        return 1
    # В остальных случаяй, считаем все возможные переходы
    return f(a - 1, b) + f(a - 3, b) + f(a // 4, b)
# Вычисляем и выводим ответ, учитывая условие
# траектория проходит через 24
print(f(38,24) * f(24,11))

Рекурсия:

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

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

Так как нужно, чтобы траектория содержала число 6, но не содержала число 12, то общее количество программ равно произведению f(3, 6) и f(6, 12). Первая часть считает количество способов дойти от 3 до 6, вторая — от 6 до 21, произведение этих значений дает ответ, так как для каждого пути из первой части можно использовать любой путь из второй части.

# Функция для подсчета количества программ преобразования a -> b
def f(a, b):
    # Если число больше целевого или равно запрещённому 12,
    # то есть нарушено условие задачи
    if a > b or a == 12:
        return 0
    # Если дошли до целевого числа,
    # то есть получили подходящую траекторию
    if a == b:
        return 1
    # В остальных случаяй, считаем все возможные переходы
    return f(a+1, b) + f(a+2, b)
# Вычисляем и выводим ответ, учитывая условие
# траектория проходит через 6
print(f(3, 6) * f(6, 21))

 

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

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

Для реализации этого способа в программе создадим список, изначально заполненный нулями. Каждое число в списке будет обозначать количество траекторий до определенного числа. Далее пройдем по списку и заполним его значениями. Значение для каждой i-ой ячейки равно сумме значений для ячеек с индексами i-1 и i-2.

По условию траектория не должна содержать число 12, поэтому при подсчете количества траекторий значение в ячейке с индексом 12 должно остаться 0. Также по условию траектория должна содержать число 6. Для этого разделим вычисления на два независимых этапа: из 3 в 6, из 6 в 21. Результаты этих этапов необходимо перемножить, чтобы получить итоговый ответ, так как для каждого пути из первой части можно использовать любой путь из второй части.

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

# Второй этап: от 6 до 21
# Массив для чисел от 0 до 21
# b[i] - количество программ, которые преобразуют число 6 в число i
b = [0] * (21 + 1)
b[6] = 1  # Начинаем из числа 6, которое должно быть в траектории
# Перебираем все числа от 7 до 21 включительно
for i in range(7, 21 + 1):
    if i == 12: # Если попадаем в число 12,
        b[i] = 0 # то ставим количество программ равным 0
    else:
        b[i] = b[i - 1] + b[i - 2]
# Общее количество программ равно произведению путей до 6 и от 6 до 21
print(a[6]*b[21])

Получается ответ:

Решение руками:

Заметим, что исходная число по условию 8. Команд, которые уменьшают число нет. По условию программа должна пройти через число 5. Мы никак не можем попасть в число 5, так как 8 никак нельзя уменьшить, следовательно, таких программ нет и ответ тогда 0.

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

Мы используем рекурсивный способ решения задачи, так как можем рассматривать каждую программу как последовательность команд, которые приводят к целевому числу. Для этого создаем функцию f(a, b), которая возвращает количество программ, преобразующих число a в число b. Внутри функции мы выполняем следующие шаги:

1. Проверяем, если текущее число a стало больше b или равно запрещённому числу 20, то такая траектория невозможна, возвращаем 0.

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

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

- один раз с аргументом a+1, что соответствует команде "прибавить 1";

- второй раз с аргументом a*2, что соответствует команде "умножить на 2".

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

Так как условие требует, чтобы траектория проходила через число 5 и не содержала число 20, мы делим решение на два этапа: от 8 до 5 и от 5 до 36. Произведение f(8, 5) * f(5, 36) даст окончательное количество программ, удовлетворяющих всем условиям.

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

# Вычисляем общее количество программ, проходящих через число 5 и не содержащих 20
print(f(8, 5) * f(5, 36))

—

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

Мы можем решить задачу динамическим способом, создавая массивы для хранения количества программ для каждого числа на траектории. Разделяем задачу на два этапа: от 8 до 5 и от 5 до 36.

1. Первый этап: от 8 до 5

- Создаем массив a длиной 37 (чтобы включить число 36).

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

- Проходим по всем индексам от 9 до 5 включительно:

      - Если число чётное, можем прийти либо командой "+1"из i-1, либо командой "*2"из i//2; суммируем эти значения в a[i].

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

2. Второй этап: от 5 до 36

- Создаем массив b длиной 37.

- Записываем b[5] = 1, начальное число 5.

- Проходим по всем индексам от 6 до 36 включительно:

      - Пропускаем число 20, так как траектория не должна его содержать.

      - Для чётных чисел добавляем суммы из b[i-1] и b[i//2].

      - Для нечётных чисел добавляем только b[i-1].

Общее количество программ равно произведению a[5] * b[36], так как каждый путь из первой части можно соединить с любым путем из второй части.

# Первый этап: от 8 до 5
a = [0] * (36 + 1)  # Создаем массив для чисел до 36 включительно
a[8] = 1  # Начальное положение — число 8
# Перебираем числа от 9 до 5 включительно
for i in range(9, 5 + 1):
    # Если число чётное, учитываем команды +1 и *2
    if i % 2 == 0:
        a[i] = a[i - 1] + a[i // 2]
    else:
        # Если число нечётное, учитываем только команду +1
        a[i] = a[i - 1]

# Второй этап: от 5 до 36
b = [0] * (36 + 1)  # Создаем массив для чисел до 36 включительно
b[5] = 1  # Начальное положение — число 5
# Перебираем числа от 6 до 36 включительно
for i in range(6, 36 + 1):
    # Пропускаем число 20, так как оно запрещено
    if i == 20:
        continue
    # Если число чётное, учитываем команды +1 и *2
    if i % 2 == 0:
        b[i] = b[i - 1] + b[i // 2]
    else:
        # Если число нечётное, учитываем только команду +1
        b[i] = b[i - 1]

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

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

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

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

Так как нужно, чтобы траектория содержала число 7, но не содержала число 15, то общее количество программ равно произведению f(2, 7) и f(7, 30). Первая часть считает количество способов дойти от 2 до 7, вторая — от 7 до 30, произведение этих значений дает ответ, так как для каждого пути из первой части можно использовать любой путь из второй части.

# Функция для подсчета количества программ преобразования a -> b
def f(a, b):
    # Если число больше целевого или равно запрещённому 15,
    # то есть нарушено условие задачи
    if a > b or a == 15:
        return 0
    # Если дошли до целевого числа,
    # то есть получили подходящую траекторию
    if a == b:
        return 1
    # В остальных случаяй, считаем все возможные переходы
    return f(a + 1, b) + f(a + 4, b) + f(a * 2, b)
# Вычисляем и выводим ответ, учитывая условие
# траектория проходит через 7
print(f(2, 7) * f(7, 30))

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

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

Для реализации этого способа в программе создадим список, изначально заполненный нулями. Каждое число в списке будет обозначать количество траекторий до определенного числа. Далее пройдем по списку и заполним его значениями. Значение для каждой i-ой ячейки равно сумме значений для ячеек с индексами i-1 (команда Прибавить 1), i-4 (команда Прибавить 4) и i//2 (команда Умножить на 2, только для четных чисел).

По условию траектория не должна содержать число 15, поэтому при подсчете количества траекторий значение в ячейке с индексом 15 должно остаться 0. Также по условию траектория должна содержать число 7. Для этого разделим вычисления на два независимых этапа: из 2 в 7, из 7 в 30. Результаты этих этапов необходимо перемножить, чтобы получить итоговый ответ, так как для каждого пути из первой части можно использовать любой путь из второй части.

# Первый этап: от 2 до 7
# Создаем массив для хранения количества путей до чисел от 0 до 7
# a[i] - количество программ, которые преобразуют число 2 в число i
a = [0] * (7 + 1)
a[2] = 1  # Исходное положение - только один способ быть в числе 2

# Перебираем все числа от 3 до 7 включительно
for i in range(3, 7 + 1):
    # Можно прийти командами Прибавить 1 и Прибавить 4
    ways = a[i-1] + a[i-4]

    # Можно прийти командой Умножить на 2 (только для четных чисел)
    if i % 2 == 0:
        ways += a[i // 2]

    a[i] = ways

# Второй этап: от 7 до 30 (с обязательным исключением числа 15)
# Массив для чисел от 0 до 30
# b[i] - количество программ, которые преобразуют число 7 в число i
b = [0] * (30 + 1)
b[7] = 1  # Начинаем из числа 7, которое должно быть в траектории

# Перебираем все числа от 8 до 30 включительно
for i in range(8, 30 + 1):
    if i == 15:
        continue  # Пропускаем число 15 согласно условию задачи

    # Можно прийти командами Прибавить 1 и Прибавить 4
    ways = b[i-1] + b[i-4]

    # Можно прийти командой Умножить на 2 (только для четных чисел)
    if i % 2 == 0:
        ways += b[i // 2]

    b[i] = ways

# Общее количество программ равно произведению путей до 7 и от 7 до 30
print(a[7] * b[30])

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

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

Для реализации этого способа в программе создадим список, изначально заполненный нулями. Каждое число в списке будет обозначать количество траекторий до определенного числа. Далее пройдем по списку и заполним его значениями. Значение для каждой i-ой ячейки равно сумме значений для ячеек с индексами i-1, i-2 и i // 2 (только для четных чисел, так как в нечетные нельзя попасть используя команду Умножь на 2).

По условию траектория не должна содержать число 7, поэтому при подсчете количества траекторий значение в ячейке с индексом 7 должно остаться 0. Также по условию траектория должна содержать число 30. Для этого разделим вычисления на два независимых этапа: из 2 в 30, из 30 в 41. Результаты этих этапов необходимо перемножить, чтобы получить итоговый ответ, так как для каждого пути из первой части можно использовать любой путь из второй части.

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

# Второй этап: от 30 до 41
# Массив для чисел от 0 до 41
# b[i] - количество программ, которые преобразуют число 30 в число i
b = [0] * (41 + 1)
b[30] = 1  # Начинаем из числа 30, которое должно быть в траектории
# Перебираем все числа от 31 до 41 включительно
for i in range(31, 41 + 1):
    if i % 2 == 0:
        # Для четных чисел учитываем все три команды
        b[i] = b[i - 1] + b[i - 2] + b[i // 2]
    else:
        # Для нечетных чисел - только команды сложения
        b[i] = b[i - 1] + b[i - 2]
# Общее количество программ равно произведению путей до 30 и от 30 до 41
print(a[30]*b[41])

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

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

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

Так как нужно, чтобы траектория содержала число 30, но не содержала число 7, то общее количество программ равно произведению f(2, 30) и f(30, 41). Первая часть считает количество способов дойти от 2 до 30, вторая — от 30 до 41, произведение этих значений дает ответ, так как для каждого пути из первой части можно использовать любой путь из второй части.

# Функция для подсчета количества программ преобразования a -> b
def f(a, b):
# Если число больше целевого или равно запрещённому 7,
    # то есть нарушено условие задачи
    if a > b or a == 7:
        return 0
    # Если дошли до целевого числа,
    # то есть получили подходящую траекторию
    if a == b:
        return 1
    # В остальных случаяй, считаем все возможные переходы
    return f(a + 1, b) + f(a + 2, b) + f(a * 2, b)
# Вычисляем и выводим ответ, учитывая условие
# траектория проходит через 30
print(f(2, 30) * f(30, 41))