23.08 Прочие прототипы

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

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

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

2. Если x равно y, возвращаем 1, что обозначает найденную подходящую программу.

3. Иначе рекурсивно суммируем количество программ для трёх возможных переходов: прибавление 2, прибавление 4 и прибавление 5.

Для нахождения числа, для которого количество программ равно 1001, мы перебираем целевые значения y начиная с 32 и проверяем результат функции f(31, y). Как только находим y, где функция возвращает 1001, выводим его.

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

# Перебираем возможные целевые числа, начиная с 32
for y in range(32, 70):
    # Если количество программ равно 1001, выводим результат
    if f(31, y) == 1001:
        print(y)

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

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

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

2. Перебираем все числа от 32 до верхней границы (100) и заполняем массив:

- Для каждого числа i считаем сумму значений a[i-2], a[i-4] и a[i-5], что соответствует прибавлению 2, 4 и 5 соответственно.

3. Если значение a[i] становится равным 1001, выводим это число и прекращаем вычисления, так как цель достигнута.

# Массив для хранения количества программ
a = [0] * 100
# Начальное число 31
a[31] = 1

# Перебираем все числа от 32 до 100
for i in range(32, 100 + 1):
    # Количество программ для i = сумма программ для i-2, i-4 и i-5
    a[i] = a[i-2] + a[i-4] + a[i-5]
    # Если нашли число с 1001 программой, выводим его
    if a[i] == 1001:
        print(i)
        break

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

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

1. Инициализируем массив достаточно большой длины, чтобы покрыть целевое число: a = [0] * 300.

2. Задаём начальные условия: a[1] = 0, так как число 1 — это начальное число, а a[0] = 10**20, чтобы предотвратить использование недостижимых чисел.

3. Перебираем все числа от 2 до 299 включительно. Для каждого числа i делаем следующие шаги:

- Инициализируем три переменные x, y, z большими числами (10**20), чтобы корректно использовать функцию min.

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

- Если i >= 5, y = a[i - 5] + 1 — если число получено прибавлением 5.

- Если i % 3 == 0, z = a[i // 3] + 1 — если число делится на 3, получаем его делением на 3 и прибавляем одну команду.

4. Для числа i выбираем минимальное значение из трёх возможных переходов: a[i] = min(x, y, z).

После заполнения массива значение a[227] будет равно длине самой короткой программы для получения числа 227 из числа 1.

# Создаем массив для хранения минимального количества команд
a = [0] * 300
# Число 0 недостижимо
a[0] = 10**20
# Исходное число 1, команд не требуется
a[1] = 0

# Перебираем все числа от 2 до 299
for i in range(2, 300):
    # Инициализируем количество команд для всех трёх возможных переходов большими числами
    x = y = z = 10**20
    # Если число получено прибавлением 1
    x = a[i - 1] + 1
    # Если число получено прибавлением 5
    if i >= 5:
        y = a[i - 5] + 1
    # Если число получено умножением на 3
    if i % 3 == 0:
        z = a[i // 3] + 1
    # Выбираем минимальное количество команд для текущего числа
    a[i] = min(x, y, z)

# Выводим длину самой короткой программы для числа 227
print(a[227])

Рекурсивный способ решения

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

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

2. Если s == fi, значит, мы достигли цели, возвращаем 1 — одна подходящая программа найдена.

3. В остальных случаях рекурсивно считаем количество программ для двух возможных команд: прибавление 2 и прибавление 5, суммируя результаты.

Далее перебираем все числа начиная с 6 и до 99. Для каждого числа проверяем, если количество программ, получаемое вызовом f(5, i), равно 34, выводим это число и завершаем поиск, так как найдено первое подходящее число.

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

# Перебираем все числа от 6 до 99
for i in range(6, 100):
    # Если количество программ равно 34, выводим число и прекращаем поиск
    if f(5, i) == 34:
        print(i)
        break

Динамический способ решения

Динамический способ позволяет избежать многократного пересчёта одних и тех же значений. Создаём массив a длиной 101, где a[i] хранит количество программ, преобразующих число 5 в число i.

1. Инициализируем массив нулями: a = [0] * 101.

2. Задаём исходное условие: a[5] = 1, так как из числа 5 в 5 можно получить число одной программой длины 0.

3. Перебираем числа от 6 до 100 включительно. Для каждого числа i делаем следующее:

- Количество программ, которые приводят к числу i, равно сумме программ, приводящих к числам i-2 и i-5, так как можно к ним прибавить соответствующую команду.

- То есть a[i] = a[i-2] + a[i-5].

4. После заполнения массива ищем индекс, где количество программ равно 34 с помощью a.index(34), и выводим его.

# Создаем массив для хранения количества программ
a = [0] * 101
# Исходное число 5, одна программа длины 0
a[5] = 1

# Перебираем числа от 6 до 100
for i in range(6, 101):
    # Количество программ для текущего числа равно сумме программ для i-2 и i-5
    a[i] = a[i - 2] + a[i - 5]

# Находим число, для которого количество программ равно 34
print(a.index(34))

Рекурсивный способ решения

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

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

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

3. В остальных случаях рекурсивно считаем количество программ для двух возможных команд: прибавить 1 и умножить на 2, суммируя результаты.

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

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

# Создаем множество для хранения чисел, для которых количество программ равно 36
a = set()
# Перебираем числа от 2 до 99
for y in range(2, 100):
    # Если количество программ равно 36, добавляем число в множество
    if f(1, y) == 36:
        a.add(y)

# Выводим минимальное число из множества
print(min(a))

Динамический способ решения

Динамический способ позволяет избежать многократного пересчета одних и тех же значений. Мы создаём массив a, где a[i] хранит количество программ, которые преобразуют число 1 в число i.

1. Инициализируем массив нулями: a = [0] * 100.

2. Задаём исходное условие: a[1] = 1, так как из числа 1 в 1 существует один путь.

3. Перебираем все числа i от 1 до 29 включительно. Для каждого числа выполняем следующие шаги:

- К числу i+1 добавляем количество программ из числа i, так как можно прибавить 1.

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

4. После заполнения массива ищем индекс числа, где количество программ равно 36 с помощью a.index(36), и выводим его.

# Создаем массив для хранения количества программ
a = [0] * 100
# Исходное число 1, одна программа длины 0
a[1] = 1

# Перебираем числа от 1 до 29
for i in range(1, 30):
    # Прибавляем к следующему числу количество программ текущего числа
    a[i + 1] += a[i]
    # Умножаем текущее число на 2 и добавляем количество программ
    a[i * 2] += a[i]

# Находим минимальное число, для которого количество программ равно 36
print(a.index(36))

Рекурсивный способ решения

Мы можем использовать рекурсивную функцию f(st), которая строит все возможные последовательности команд, начиная с числа st, и подсчитывает количество полученных чисел длины 10.

1. Создаём глобальную переменную count для хранения количества подходящих программ.

2. В функции f(st) проверяем:

- Если длина строки st равна 10, увеличиваем count на 1 и выводим строку.

- Если длина строки меньше 10, выполняем рекурсивные вызовы для обеих команд:

- Приписываем "0"справа: st + "0".

- Приписываем копию числа задом наперед: st + st[::-1].

3. Запускаем рекурсию с начального числа "7".

4. После завершения рекурсии выводим значение count.

# Инициализируем глобальный счетчик количества программ
count = 0
# Определяем рекурсивную функцию для построения всех программ
def f(st):
    global count
    # Если длина строки равна 10, найдено подходящее число
    if len(st) == 10:
        count += 1
        print(st)
    # Если длина строки меньше 10, продолжаем применять команды
    if len(st) < 10:
        # Приписываем ’0’ справа
        f(st + "0")
        # Приписываем копию числа задом наперед
        f(st + st[::-1])

# Запускаем рекурсию с числа ’7’
f("7")
# Выводим общее количество программ
print(count)

Динамический способ решения

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

1. Инициализируем массив ans пустым списком и счетчик otv = 0.

2. Добавляем начальное число "7"в ans.

3. Перебираем последовательность операций (до 1000 итераций, достаточно для достижения длины 10):

- Создаем новый список can_get для хранения результатов следующего шага.

- Для каждой строки i из ans выполняем:

- Если длина строки равна 10, увеличиваем otv на 1.

- Применяем первую команду: приписываем "0"справа. Если длина новой строки не превышает 10, добавляем в can_get.

- Применяем вторую команду: приписываем копию строки задом наперед. Если длина новой строки не превышает 10, добавляем в can_get.

- Если список can_get пуст, прекращаем цикл.

- Иначе присваиваем ans = can_get для следующей итерации.

4. После завершения цикла выводим otv — общее количество программ.

# Инициализируем список для хранения текущих строк
ans = []
# Счетчик количества программ длины 10
otv = 0
# Добавляем начальное число ’7’
ans.append("7")

# Перебираем операции (ограничение по числу итераций)
for operations in range(1000):
    # Список для хранения новых строк после текущей итерации
    can_get = []
    # Обрабатываем каждую строку из текущего списка
    for i in ans:
        # Если длина строки равна 10, увеличиваем счетчик
        if len(i) == 10:
            otv += 1
        # Применяем команду приписать ’0’ справа
        new_st = i + "0"
        if len(new_st) <= 10:
            can_get.append(new_st)
        # Применяем команду приписать копию строки задом наперед
        new_st = i + i[::-1]
        if len(new_st) <= 10:
            can_get.append(new_st)
    # Если новые строки не получены, прекращаем цикл
    if len(can_get) == 0:
        break
    # Обновляем список текущих строк
    ans = can_get

# Выводим общее количество программ длины 10
print(otv)

Стоит сказать, что динамическое решение получается довольно трудоемким и громоздким, поэтому рекомендуется использовать рекурсивную реализацию в данной задаче.

Рекурсивный способ решения

Мы определяем рекурсивную функцию f(st, fn, count_2, count_3), которая подсчитывает количество программ, ведущих из числа st в число fn, учитывая сколько раз уже использовались команды 2 и 3.

1. В функции проверяем:

- Если текущее число st равно целевому числу fn и количество использований команды 3 больше, чем команды 2, возвращаем 1 — программа подходит.

- Если st больше fn, программа не подходит, возвращаем 0.

2. Создаём рекурсивные вызовы для каждой команды:

- x = f(st + 3, fn, count_2, count_3) — прибавление 3 не меняет счетчики команд 2 и 3.

- y = f(st * 2, fn, count_2 + 1, count_3) — умножение на 2 увеличивает счетчик команды 2 на 1.

- Для команды 3 создаём массив из 10 элементов z[i], каждый элемент соответствует добавлению цифры от 0 до 9: st * 10 + i, увеличивая счетчик команды 3 на 1.

3. Возвращаем сумму результатов всех возможных веток: return x + y + sum(z).

4. Запускаем функцию с начального числа 1 и счетчиков команд 2 и 3 равных нулю. Выводим результат.

# Рекурсивная функция подсчета количества программ
def f(st, fn, count_2, count_3):
    # Если текущее число равно целевому и команда 3 встречается чаще, программа подходит
    if st == fn and count_3 > count_2:
        return True
    # Если текущее число больше целевого, программа невозможна
    if st > fn:
        return False
    # Применяем команду 1: прибавляем 3
    x = f(st + 3, fn, count_2, count_3)
    # Применяем команду 2: умножаем на 2, увеличиваем счетчик команды 2
    y = f(st * 2, fn, count_2 + 1, count_3)
    # Применяем команду 3: приписываем любую цифру от 0 до 9 справа
    z = [0] * 10
    for i in range(10):
        z[i] = f(st * 10 + i, fn, count_2, count_3 + 1)
    # Возвращаем сумму всех возможных вариантов
    return x + y + sum(z)

# Вычисляем и выводим количество подходящих программ
print(f(1, 48, 0, 0))

Динамический способ решения

Динамический способ использует множество ans, где храним кортежи (текущее число, счетчик команды 2, счетчик команды 3) для всех возможных состояний:

1. Инициализируем ans = set() и добавляем стартовое состояние (1, 0, 0).

2. Задаем переменную otv = 0 для подсчета подходящих программ.

3. Выполняем цикл с достаточно большим числом итераций (например, 1000):

- Создаем пустое множество can_get для хранения новых состояний.

- Для каждого состояния i из ans:

- Распаковываем a, cnt_2, cnt_3.

- Если a == 48 и cnt_3 > cnt_2, увеличиваем otv на 1 и продолжаем.

- Применяем команду 1: если a + 3 <= 48, добавляем новое состояние.

- Применяем команду 2: если a * 2 <= 48, добавляем новое состояние с увеличением счетчика команды 2.

- Применяем команду 3: приписываем цифры 0–9 справа, если результат не превышает 48, добавляем новое состояние с увеличением счетчика команды 3.

- Если can_get пуст, прекращаем цикл.

- Иначе присваиваем ans = can_get для следующей итерации.

4. После завершения цикла выводим otv — количество подходящих программ.

# Инициализация множества для текущих состояний
ans = set()
# Стартовое состояние: число 1, счетчики команд 2 и 3 равны 0
ans.add((1, 0, 0))
# Переменная для подсчета подходящих программ
otv = 0

# Основной цикл перебора возможных операций
for operations in range(1000):
    # Множество для хранения новых состояний после текущей итерации
    can_get = set()
    # Перебираем все текущие состояния
    for i in ans:
        a, cnt_2, cnt_3 = i
        # Если достигли числа 48 и команда 3 встречается чаще команды 2, считаем программу
        if (a == 48) and (cnt_2 < cnt_3):
            otv += 1
            continue
        # Применяем команду 1: прибавляем 3
        if a + 3 <= 48:
            can_get.add((a + 3, cnt_2, cnt_3))
        # Применяем команду 2: умножаем на 2
        if a * 2 <= 48:
            can_get.add((a * 2, cnt_2 + 1, cnt_3))
        # Применяем команду 3: приписываем цифры 0–9 справа
        for j in range(10):
            new_numb = int(str(a) + str(j))
            if new_numb <= 48:
                can_get.add((new_numb, cnt_2, cnt_3 + 1))
    # Если новые состояния не получены, завершаем цикл
    if len(can_get) == 0:
        break
    # Обновляем текущее множество состояний
    ans = can_get

# Выводим количество подходящих программ
print(otv)

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

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

1. Сначала определяем вспомогательную функцию sum_of_digits(number), которая считает сумму цифр числа.

- Если число равно 0, возвращаем 0.

- Иначе берем последнюю цифру числа через оператор % 10 и прибавляем результат рекурсивного вызова для числа без последней цифры (целочисленное деление на 10).

- Мы используем @lru_cache(None), чтобы кешировать результаты вызовов функции и ускорить вычисления при повторных обращениях к одной и той же сумме цифр.

2. В функции f(a, b) проверяем следующие условия:

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

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

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

      - прибавляем 1 к и вызываем функцию рекурсивно,

      - умножаем на 3 и вызываем функцию рекурсивно,

      - прибавляем сумму цифр числа (через функцию sum_of_digits(a)) и вызываем функцию рекурсивно.

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

3. Запускаем функцию f(11, 60), чтобы получить количество всех программ, которые начинают с числа 11 и приводят к числу 60.

# Импортируем декоратор для кэширования функций
from functools import lru_cache

# Определяем функцию для подсчета суммы цифр числа с кэшированием
@lru_cache(None)
def sum_of_digits(number):
    # Если число равно 0, сумма цифр равна 0
    if number == 0:
        return 0
    else:
        # Суммируем последнюю цифру и рекурсивно вызываем для числа без последней цифры
        return number % 10 + sum_of_digits(number // 10)

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

# Вызываем функцию для подсчета всех программ от 11 до 60
print(f(11, 60))

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

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

Мы определяем функцию f(start, finish, limits, visited), где: - start — текущее число, на котором находится исполнитель; - finish — число, до которого нужно дойти; - limits — кортеж, содержащий минимальное и максимальное допустимое число на экране; - visited — множество чисел, которые уже были посещены, чтобы не допустить повторов.

Шаг за шагом алгоритм работает следующим образом:

1. Проверяем, достигли ли мы цели:

- Если start == finish, мы нашли одну допустимую программу и возвращаем 1.

2. Проверяем границы:

- Если start меньше limits[0] или больше limits[1], путь невозможен и возвращаем 0.

3. Проверяем повторное посещение:

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

4. Если ни одно из условий не выполнено:

- Создаем копию множества visited и добавляем текущее число в неё, чтобы отслеживать посещенные позиции на этом ветвлении рекурсии.

- Рекурсивно считаем количество программ, используя первую команду (start + 4) и вторую команду (start - 5).

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

5. Запускаем функцию с начальными значениями start=1, finish=20, limits=(-20,40) и пустым множеством visited.

# Определяем рекурсивную функцию для подсчета программ
def f(start, finish, limits, visited):
    # Если достигли целевого числа, возвращаем 1
    if (start == finish):
        return 1
    # Если текущее число вышло за границы допустимого интервала, возвращаем 0
    if (start < limits[0]) or (start > limits[1]):
        return 0
    # Если текущее число уже посещено, возвращаем 0
    if (start in visited):
        return 0
    # Создаем копию множества посещенных чисел и добавляем текущее число
    vis = visited.copy()
    vis.add(start)
    # Считаем количество программ, если выполнить команду "прибавить 4"
    x = f(start + 4, finish, limits, vis)
    # Считаем количество программ, если выполнить команду "вычесть 5"
    y = f(start - 5, finish, limits, vis)
    # Общее количество программ для текущего числа — сумма двух вариантов
    return x + y

# Запускаем функцию от 1 до 20 с указанными границами и пустым множеством посещенных чисел
print(f(1, 20, (-20, 40), set()))

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

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

Далее выполняем итеративный цикл по количеству операций (здесь ограничиваем до 1000 шагов, чтобы цикл завершился):

1. Создаем пустой список can_get, куда будем добавлять все новые состояния, достижимые на этом шаге.

2. Перебираем каждое текущее состояние из списка ans:

- Если текущее число равно целевому 20, увеличиваем на 1 и продолжаем к следующему состоянию.

- Иначе создаем две копии множества посещённых чисел: vis_first и vis_second для двух возможных команд.

- Проверяем возможность хода "прибавить 4": число не должно быть уже посещено и не должно превышать верхнюю границу 40. Если допустимо, добавляем новое число в множество и заносим в список возможных следующих состояний.

- Проверяем возможность хода "вычесть 5": число не должно быть уже посещено и не должно быть меньше нижней границы -20. Если допустимо, добавляем новое число в множество и заносим в список возможных следующих состояний.

3. Если после обработки всех состояний на шаге can_get пустой, значит новых ходов нет, выходим из цикла.

4. Обновляем ans новым списком can_get для следующей итерации.

После завершения цикла в переменной otv будет храниться общее количество допустимых программ из числа 1 в число 20.

# Инициализируем список ans состоянием: текущее число 1 и множество {1}
ans = []
ans.append((1, set([1])))
# Инициализируем счетчик ответов
otv = 0
# Ограничение на количество операций
for operations in range(1000):
    # Создаем пустой список для новых состояний
    can_get = []
    # Перебираем все текущие состояния
    for i in ans:
        a, vis = i
        # Создаем две копии множества посещённых чисел
        vis_first = vis.copy()
        vis_second = vis.copy()
        # Если текущее число достигло цели, увеличиваем ответ
        if a == 20:
            otv += 1
            continue
        # Проверяем возможность прибавить 4
        if ((a + 4) in vis) == 0 and (a + 4 <= 40):
            vis_first.add(a + 4)
            can_get.append((a + 4, vis_first))
        # Проверяем возможность вычесть 5
        if ((a - 5) in vis) == 0 and (a - 5 >= -20):
            vis_second.add(a - 5)
            can_get.append((a - 5, vis_second))
    # Если новых ходов нет, выходим из цикла
    if len(can_get) == 0:
        break
    # Обновляем список состояний для следующей итерации
    ans = can_get
# Выводим итоговое количество программ
print(otv)

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

Мы используем рекурсию для подсчёта всех возможных программ. Идея заключается в том, что мы создаём функцию f(st, fn), где st — текущее двоичное число в виде строки, fn — целевое число в двоичной системе.

1. Проверяем, достигли ли мы цели:

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

2. Проверяем невозможные ситуации:

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

3. Иначе считаем два возможных хода:

- Первый ход: приписать 1 справа, формируем новую строку st + "1" и рекурсивно вызываем функцию.

- Второй ход: определяем бит четности (количество нулей в st по модулю 2).

      - Если количество нулей чётное, приписываем 0 справа и рекурсивно вызываем функцию для st + "0".

      - Если количество нулей нечётное, приписываем 1 слева и рекурсивно вызываем функцию для "1"+ st.

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

# Определяем рекурсивную функцию f(st, fn)
def f(st, fn):
    # Если текущее число совпало с целевым, возвращаем 1
    if st == fn:
        return 1
    # Если длина текущей строки больше длины целевого числа, путь невозможен
    if len(st) > len(fn):
        return 0
    # Считаем путь, где мы приписываем 1 справа
    x = f(st + "1", fn)
    # Считаем путь с использованием команды "бит четности"
    if st.count("0") % 2 == 0:
        # Если количество нулей чётное, приписываем 0 справа
        y = f(st + "0", fn)
    else:
        # Если количество нулей нечётное, приписываем 1 слева
        y = f("1" + st, fn)
    # Складываем оба возможных пути
    return x + y

# Запускаем функцию от "1" до "1011111" (95 в двоичной)
print(f("1", "1011111"))

—

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

Мы используем динамику, чтобы последовательно подсчитать количество программ для каждого числа от 1 до 95.

1. Сначала создаём функцию to_bin(n), которая переводит число из десятичной системы в двоичную:

- Инициализируем пустую строку a.

- Пока число :

      - Берём остаток от деления на 2 и добавляем его слева к строке a.

      - Делим на 2 целочисленно.

- Возвращаем строку a, которая является двоичным представлением числа.

2. Создаём массив a размером 96 (для чисел от 0 до 95), изначально заполненный нулями.

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

4. Для каждого числа i от 1 до 94:

- Переводим его в двоичное представление cur_num = to_bin(i).

- Применяем первую команду: приписываем 1 справа, получаем новое число new_num = int(cur_num + "1base=2).

- Если new_num < 96, увеличиваем a[new_num] на количество программ для i.

- Определяем бит четности chet_bit = cur_num.count("0") % 2.

      - Если chet_bit == 1, приписываем 1 слева, иначе приписываем 0 справа.

      - Получаем новое число new_num и, если оно меньше 96, увеличиваем a[new_num] на количество программ для i.

5. В ячейке a[95] хранится общее количество программ, которые переводят число 1 в 95.

# Функция для перевода десятичного числа в двоичное
def to_bin(n):
    a = ""
    while n > 0:
        a = str(n % 2) + a
        n //= 2
    return a

# Массив для хранения количества программ для каждого числа
a = [0] * 96
# Начальное число 1, один способ
a[1] = 1

# Перебираем все числа от 1 до 94
for i in range(1, 95):
    # Переводим число i в двоичное представление
    cur_num = to_bin(i)
    # Применяем команду "приписать 1 справа"
    new_num = int(cur_num + "1", base=2)
    if new_num < 96:
        a[new_num] += a[i]
    # Определяем бит четности
    chet_bit = cur_num.count("0") % 2
    if chet_bit:
        # Если бит нечётный, приписываем 1 слева
        new_num = int("1" + cur_num, base=2)
    else:
        # Если бит чётный, приписываем 0 справа
        new_num = int(cur_num + "0", base=2)
    if new_num < 96:
        a[new_num] += a[i]

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

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

Мы используем рекурсивную функцию , которая считает количество программ, переводящих текущую координату в конечную . Идея такова:

1. Если текущие координаты совпадают с конечными , то найден один путь, возвращаем 1. 2. Если текущие координаты превышают конечные по или , путь невозможен, возвращаем 0. 3. В остальных случаях мы рассматриваем все возможные действия: - Увеличиваем на 2 и рекурсивно считаем пути из - Умножаем на 2 и рекурсивно считаем пути из - Двигаемся вверх на все возможные значения от 1 до и суммируем пути из для каждого

Мы используем lru_cache для мемоизации, чтобы повторные вызовы с одинаковыми координатами не вычислялись заново. Рекурсивный вызов f((1,2),(12,19)) вернет общее количество программ.

# Импортируем декоратор для кеширования результатов рекурсии
from functools import lru_cache

# Определяем рекурсивную функцию f(st, fn), где st - текущие координаты, fn - конечные
@lru_cache(None)
def f(st, fn):
    # Если достигли конечной точки, возвращаем 1
    if st == fn:
        return 1
    # Если текущие координаты вышли за пределы конечных, возвращаем 0
    if st[0] > fn[0] or st[1] > fn[1]:
        return 0
    # Считаем количество программ при увеличении X на 2
    c1 = f((st[0] + 2, st[1]), fn)
    # Считаем количество программ при умножении X на 2
    c2 = f((st[0] * 2, st[1]), fn)
    # Создаем список для подсчета вариантов движения вверх
    c = [0] * (fn[1] - st[1] + 1)
    # Перебираем все возможные вертикальные перемещения вверх
    for i in range(1, fn[1] - st[1] + 1):
        c[i] = f((st[0], st[1] + i), fn)
    # Суммируем все возможные варианты
    return c1 + c2 + sum(c)

# Вычисляем и выводим количество программ от (1,2) до (12,19)
print(f((1, 2), (12, 19)))

—

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

Мы создаем двумерный массив , где и — координаты, а — количество программ, ведущих из начальной точки в .

1. Инициализируем массив нулями и присваиваем , так как стартуем из точки (1,2) одним способом. 2. Проходим по всем координатам от 1 до 12 и от 2 до 19: - Если , добавляем к - Если , добавляем к - Для вертикального движения перебираем все координаты от до 19 и добавляем к

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

# Создаем двумерный массив для координат от 0 до 12 по X и от 0 до 19 по Y
dp = [[0] * 20 for i in range(13)]
# Инициализация стартовой точки
dp[1][2] = 1
# Перебираем все координаты X
for x in range(1, 13):
    # Перебираем все координаты Y
    for y in range(2, 20):
        # Если можно увеличить X на 2, добавляем количество программ
        if x + 2 < 13:
            dp[x + 2][y] += dp[x][y]
        # Если можно умножить X на 2, добавляем количество программ
        if x * 2 < 13:
            dp[x * 2][y] += dp[x][y]
        # Перебираем вертикальные перемещения вверх
        for to in range(y + 1, 20):
            dp[x][to] += dp[x][y]

# Выводим количество программ, ведущих из (1,2) в (12,19)
print(dp[12][19])

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

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

1. Сначала определяем вспомогательную функцию is_prime(n), которая проверяет, является ли число простым.

- Проходим по всем числам от 2 до квадратного корня из включительно.

- Если делится на любое из этих чисел, возвращаем False.

- Иначе возвращаем True, если .

2. В функции f проверяем ограничения:

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

- Если текущее число st простое, добавляем его в множество set_prime.

- Если длина множества простых чисел равна 8, обновляем глобальное минимальное количество команд count и возвращаемся.

3. Рекурсивно вызываем функцию для каждого возможного перехода:

- st + 3 (команда 1) с увеличением count_operation на 1.

- st * 2 - 1 (команда 2) с увеличением count_operation на 1.

- Если st > 9, выполняем реверс числа, прибавляем 1 (команда 3) и вызываем функцию рекурсивно.

4. Инициализируем глобальную переменную count большим числом, запускаем рекурсию с st = 2, count_operation = 0, set() и выводим count в конце.

# Функция проверки простого числа
def is_prime(n):
    # Проходим по всем числам от 2 до квадратного корня из n включительно
    for i in range(2, int(n ** 0.5) + 1):
        # Если n делится на i, то число не простое
        if n % i == 0:
            return False
    # Если делителей нет и n>1, число простое
    return n > 1

# Рекурсивная функция для перебора программ
def f(st, count_operation, set_prime):
    global count
    # Если текущее количество команд больше найденного минимального, выходим
    if count_operation > count:
        return
    # Если текущее число простое, добавляем его в множество
    if is_prime(st):
        set_prime.add(st)
    # Если в множестве уже 8 простых чисел, обновляем минимальное количество команд
    if len(set_prime) == 8:
        count = min(count, count_operation)
        return
    # Пробуем первый вариант команды: прибавить 3
    f(st + 3, count_operation + 1, set_prime.copy())
    # Пробуем второй вариант команды: умножить на 2 и вычесть 1
    f(st * 2 - 1, count_operation + 1, set_prime.copy())
    # Пробуем третий вариант команды: реверс + 1, только если st > 9
    if st > 9:
        f(int(str(st)[::-1]) + 1, count_operation + 1, set_prime.copy())

# Инициализируем минимальное количество команд большим числом
count = 10000000000
# Запускаем рекурсию с начальным числом 2, 0 команд, пустое множество простых чисел
f(2, 0, set())
# Выводим минимальное количество команд
print(count)

—

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

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

1. Сначала создаем массив primes длиной 100000, где каждый элемент указывает, простое число или нет.

- Проходим по всем числам от 2 до 99999, проверяем простоту через функцию is_prime, заполняем массив единицами для простых чисел.

2. Инициализируем список ans с начальным состоянием (2,1), так как стартовое число 2 простое.

3. Для каждого количества операций (от 0 до 1000) строим новый список can_get:

- Для каждого состояния (a, pr) проверяем, если уже достигли 8 простых чисел, сохраняем текущий номер операций как ответ и завершаем цикл.

- Иначе добавляем все возможные новые состояния:

      - a + 3, pr + primes[a + 3]       - a * 2 - 1, pr + primes[a * 2 - 1]       - Если a > 9, выполняем реверс и +1, добавляем new_num, pr + primes[new_num]

4. После перебора всех операций выводим минимальное количество команд.

# Функция проверки простого числа
def is_prime(n):
    if n < 2:
        return 0
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            return 0
    return 1

# Массив для отметки простых чисел от 0 до 99999
primes = [0] * 100000
# Заполняем массив единицами для простых чисел
for i in range(2, 100000):
    if is_prime(i):
        primes[i] = 1

# Начальное состояние: число 2, уже одно простое число
ans = []
ans.append((2, 1))
otv, flag = 100000000, 0

# Перебираем количество операций до 1000
for operations in range(1000):
    can_get = []
    # Проходим по всем состояниям на текущем шаге
    for i in ans:
        a, pr = i
        # Если уже достигли 8 простых чисел, сохраняем результат
        if pr == 8:
            otv = operations
            flag = 1
            break
        # Добавляем новые состояния с каждой командой
        can_get.append((a + 3, pr + primes[a + 3]))
        can_get.append((a * 2 - 1, pr + primes[a * 2 - 1]))
        if a > 9:
            s = str(a)
            s = s[::-1]
                                                                                                     
                                                                                                     
            new_num = int(s) + 1
            can_get.append((new_num, pr + primes[new_num]))
    if flag:
        break
    # Обновляем список состояний для следующей итерации
    ans = can_get

# Выводим минимальное количество команд
print(otv)

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

Идея рекурсивного решения заключается в построении функции f(st, fn, en, comand), которая рассматривает все возможные последовательности команд для достижения цели и одновременно отслеживает оставшуюся энергию и количество сделанных ходов.

1. Мы создаем функцию с аргументами:

- st — текущая ступенька, на которой находится исполнитель;

- fn — целевая ступенька, на которую нужно попасть (в нашем случае 25);

- en — количество оставшейся энергии;

- comand — количество использованных команд.

2. Внутри функции выполняются следующие проверки:

- Если st == fn и энергия en >= 0, значит мы достигли цели:

- Если текущее количество команд меньше глобального минимального, обновляем минимальное количество команд и сохраняем текущую энергию.

- Если текущее количество команд равно глобальному минимальному и энергия больше сохранённой, обновляем максимальную энергию.

- Возвращаемся из функции, так как дальнейшие шаги не нужны.

- Если en < 0, то дальнейшие шаги невозможны, функция также завершает выполнение.

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

- Подняться на одну ступеньку и потратить 1 единицу энергии (f(st + 1, fn, en - 1, comand + 1));

- Подняться на две ступеньки и потратить 3 единицы энергии (f(st + 2, fn, en - 3, comand + 1));

- Подняться на три ступеньки и потратить 6 единиц энергии (f(st + 3, fn, en - 6, comand + 1)).

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

5. Изначально глобальные переменные:

- count — большое число для минимизации команд,

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

6. Запускаем функцию с начальными параметрами: первая ступенька, целевая 25-я, 60 единиц энергии и 0 команд. После завершения рекурсии выводим найденные значения минимального числа команд и максимальной энергии.

# Импортируем кэширование для ускорения рекурсии
from functools import lru_cache

# Создаем функцию f с аргументами: текущая ступенька st, конечная fn, энергия en, количество команд comand
@lru_cache(None)
def f(st, fn, en, comand):
    # Если достигли цели и энергия не отрицательна
    global count, ener
    if st == fn and en >= 0:
        # Если текущее количество команд меньше минимального
        if comand < count:
            count = comand
            ener = en
        # Если количество команд совпадает, выбираем максимум энергии
        elif comand == count and en > ener:
            ener = en
        # Завершаем текущий путь
        return
    # Если энергии недостаточно для дальнейших шагов
    if en < 0:
        return
    # Пробуем все три возможные команды и рекурсивно считаем результаты
    f(st + 1, fn, en - 1, comand + 1)
    f(st + 2, fn, en - 3, comand + 1)
    f(st + 3, fn, en - 6, comand + 1)

# Инициализация глобальных переменных
count = 10000000  # минимальное количество команд
ener = -1         # максимальная энергия для минимального количества команд

# Запускаем рекурсивную функцию с начальной позиции
f(1, 25, 60, 0)

# Выводим найденные минимальное количество команд и максимальную оставшуюся энергию
print(count, ener)

—

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

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

1. Создаем список ans и помещаем туда начальное состояние: первая ступенька, 60 единиц энергии, 0 команд.

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

3. После обработки всех состояний нового уровня копируем их в ans для следующей итерации.

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

# Инициализация списка достижимых состояний
ans = []
ans.append((1, 60, 0))  # (текущая ступенька, энергия, количество команд)

# Инициализация переменных для хранения ответа
otv, mn_com = -100000000, 100000000

# Цикл по возможным уровням ходов
for operations in range(1000):
    can_get = []
    for i in ans:
        step, energy, go = i
        # Пропускаем недопустимые состояния
        if (step > 25) or (energy < 0):
            continue
        # Если достигли цели
        if (step == 25) and (energy >= 0):
            if mn_com == go:  # одинаковое минимальное количество команд
                mn_com = go
                otv = max(otv, energy)
                continue
            elif mn_com > go:  # нашли меньшее количество команд
                mn_com = go
                otv = energy
                continue
        # Добавляем все возможные ходы
        can_get.append((step + 1, energy - 1, go + 1))
        can_get.append((step + 2, energy - 3, go + 1))
        can_get.append((step + 3, energy - 6, go + 1))
    # Если новых ходов нет, выходим из цикла
    if len(can_get) == 0:
        break
    ans = can_get.copy()

# Выводим минимальное количество команд и максимальную сохранённую энергию
print(mn_com, otv)

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

Мы используем рекурсивный подход, который позволяет проверить все возможные последовательности команд от числа 10 до числа 300 и определить минимальное количество посещённых простых чисел.

1. Сначала мы определяем функцию is_prime(n), которая проверяет, является ли число простым.

- Перебираем все числа от 2 до квадратного корня из включительно.

- Если делится на любое из этих чисел, оно составное, возвращаем False.

- Если делителей не найдено и , возвращаем True.

2. Далее определяем рекурсивную функцию f(st, fn, primes) с кэшированием lru_cache, чтобы избежать повторных вычислений для одинаковых аргументов.

- st — текущее число,

- fn — конечное число,

- primes — количество посещённых простых чисел на текущем пути.

3. В теле функции проверяем:

- Если текущее число st простое, увеличиваем счётчик primes на 1.

- Если st == fn, значит мы достигли конечного числа:

      - Если текущее значение primes меньше глобального минимального count, обновляем count.

      - Возвращаемся из функции, так как дальнейшие шаги не нужны.

- Если st > fn, дальнейшие шаги не ведут к цели, возвращаемся.

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

- st + 1 — прибавить 1

- st * 2 + 1 — умножить на 2 и прибавить 1

- st * 2 - 1 — умножить на 2 и вычесть 1

- st * 4 + 1 — умножить на 4 и прибавить 1

5. После запуска рекурсии с начального числа 10 и конечного 300, глобальная переменная count будет содержать минимальное количество посещённых простых чисел.

# Функция проверки простого числа
def is_prime(n):
    # Перебираем все числа от 2 до квадратного корня из n
    for i in range(2, int(n ** 0.5) + 1):
        # Если делится на i, число не простое
        if n % i == 0:
            return False
    # Число простое, если оно не 1
    return n != 1

# Подключаем кэширование для рекурсивной функции
from functools import lru_cache

@lru_cache(None)
def f(st, fn, primes):
    # Если текущее число простое, увеличиваем счетчик primes
    global count
    if is_prime(st):
        primes += 1
    # Если дошли до конечного числа
    if st == fn:
        # Обновляем минимальное количество посещенных простых чисел
        if primes < count:
            count = primes
        return
    # Если текущее число больше конечного, возвращаемся
    if st > fn:
        return
    # Рекурсивно вызываем функцию для всех четырех команд
    f(st + 1, fn, primes)
    f(st * 2 + 1, fn, primes)
    f(st * 2 - 1, fn, primes)
    f(st * 4 + 1, fn, primes)

# Инициализируем глобальную переменную count очень большим числом
count = 100000000000
# Запускаем рекурсию от числа 10 до 300
f(10, 300, 0)
                                                                                                     
                                                                                                     
# Выводим минимальное количество посещенных простых чисел
print(count)

—

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

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

1. Сначала определяем функцию is_prime(n) для проверки простоты чисел.

- Если , возвращаем 0 (не простое).

- Перебираем все числа от 2 до квадратного корня из включительно.

- Если делится на любое из этих чисел, возвращаем 0.

- Иначе возвращаем 1, число простое.

2. Создаём два массива длиной 301:

- a[i] — минимальное количество простых чисел, которое можно посетить, чтобы добраться до числа .

- primes[i] — является ли число простым (1 — простое, 0 — нет).

3. Инициализируем:

- Все значения a[i] большим числом, кроме стартового числа 10, для которого a[10] = 0.

- Для каждого числа от 2 до 300 проверяем простоту и заполняем массив primes[i].

4. Для каждого числа от 10 до 299 обновляем минимальное количество посещённых простых чисел для всех чисел, до которых можно попасть командой:

-

- , если меньше 301

- , если меньше 301

- , если меньше 301

При этом к значению a[i] добавляется primes[target], чтобы учесть, посещено ли новое число простым.

5. После прохода по всем числам a[300] содержит минимальное количество посещённых простых чисел для пути от 10 до 300.

# Функция проверки простого числа
def is_prime(n):
    # Если число меньше 2, не простое
    if n < 2:
        return 0
    # Перебираем числа от 2 до квадратного корня из n
    for i in range(2, int(n ** 0.5) + 1):
        # Если делится на i, число не простое
        if n % i == 0:
            return 0
    # Число простое
    return 1

# Инициализация массивов
a, primes = [10000000] * 301, [0] * 301
# Стартовое число 10 имеет 0 посещенных простых чисел
a[10] = 0

# Заполняем массив простых чисел
for i in range(2, 301):
    if is_prime(i):
        primes[i] = 1

# Динамическое вычисление минимального количества простых чисел
for i in range(10, 300):
    # Переход командой +1
    a[i + 1] = min(a[i + 1], a[i] + primes[i + 1])
    # Переход командой *2 + 1
    if i * 2 + 1 < 301:
        a[i * 2 + 1] = min(a[i * 2 + 1], a[i] + primes[i * 2 + 1])
    # Переход командой *2 - 1
    if i * 2 - 1 < 301:
        a[i * 2 - 1] = min(a[i * 2 - 1], a[i] + primes[i * 2 - 1])
    # Переход командой *4 + 1
    if i * 4 + 1 < 301:
        a[i * 4 + 1] = min(a[i * 4 + 1], a[i] + primes[i * 4 + 1])

# Выводим минимальное количество посещенных простых чисел при достижении 300
                                                                                                     
                                                                                                     
print(a[300])

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

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

dp = [[0] * 5 for _ in range(16 * 20 + 1)]
dp[10][0] = 1
for cnt in range(5):
    for x in range(16 * 20 + 1):
        if x + 1 <= 16 * 20:
            dp[x + 1][cnt] += dp[x][cnt]
        if x % 2 == 0 and cnt + 1 < 5:
            dp[x // 2][cnt + 1] += dp[x][cnt]
print(sum(dp[20]))

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

Мы используем рекурсивный подход с подсчетом количества программ. Идея решения заключается в том, что мы создаем функцию f(st, end, cnt), где:

- st — текущее число на экране,

- end — целевое число,

- cnt — количество применений второй команды (деления на 2) в текущей программе.

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

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

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

3. Если текущее число равно целевому (st == end), то мы нашли корректную программу, возвращаем 1, но при этом продолжаем проверять возможность применения второй команды еще раз, если число четное.

4. Если текущее число четное, можем применить обе команды:

- применяем первую команду (st+1) без увеличения счетчика cnt,

- применяем вторую команду (st//2) и увеличиваем cnt на 1, суммируем количество программ из этих двух вариантов.

5. Если текущее число нечетное, можем применить только первую команду (st+1).

Для ускорения вычислений мы используем кэширование результатов с помощью декоратора @lru_cache(None), чтобы не пересчитывать одни и те же вызовы функции.

Вызов f(10, 20, 0) запускает рекурсию с начального числа 10, целевого числа 20 и счетчика применений второй команды равного 0.

# Импортируем инструмент для кэширования вызовов функции
from functools import lru_cache

# Декоратор кэширует все результаты функции, чтобы не пересчитывать одинаковые параметры
@lru_cache(None)
def f(st, end, cnt):
    # Если текущее число стало слишком большим, путь невозможен
    if (st > 20*16):
        return 0
    # Если количество применений второй команды превысило 4, путь невозможен
    if (cnt > 4):
        return 0
    # Если текущее число равно целевому
    if (st == end):
        # Считаем этот путь, но продолжаем проверку возможности применения второй команды
        return 1 + f(st//2,end,cnt+1) + f(st+1, end, cnt)
    # Если число четное, можем применить обе команды
    if (st%2 == 0):
        # Первый вариант: прибавляем 1, счетчик второй команды не меняется
        # Второй вариант: делим на 2, увеличиваем счетчик второй команды
        return f(st+1, end, cnt) + f(st//2, end, cnt+1)
    else:
        # Если число нечетное, можно применить только прибавление 1
        return f(st+1, end, cnt)

# Вызываем функцию с начального числа 10, целевого 20, счетчик второй команды равен 0
# И выводим результат — количество программ, удовлетворяющих условиям
print(f(10,20,0))

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

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

1. Проверка выхода за пределы:

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

2. Проверка достижения цели:

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

3. Рекурсивный подсчет возможных переходов:

- Мы создаем переменную s = 0, которая будет накапливать количество программ.

- Если предыдущей командой не была команда 1 (c != 1), мы вызываем рекурсивно функцию с , , и указываем, что предыдущей командой теперь является 1.

- Если предыдущей командой не была команда 2 (c != 2), вызываем функцию с , , и c = 2.

- Если предыдущей командой не была команда 3 (c != 3), вызываем функцию с , , и c = 3.

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

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

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

# Вызываем функцию для исходного числа 4 и целевого 174
print(f(4, 174))

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

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

- — текущее число на экране,

- — целевое число,

- — номер команды, использованной на предыдущем шаге,

- — номер команды, использованной два шага назад.

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

- если , дальнейшее выполнение команд невозможно, возвращаем ;

- если , значит достигнут результат, возвращаем .

Далее вычисляем единицы и десятки числа :

- — цифра единиц,

- — цифра десятков.

Для каждой команды проверяем:

- Если команда не была выполнена два шага назад (c2 != номер команды) и применение команды изменит число и не приведет к 0, то рекурсивно вызываем функцию с новым значением числа и обновленными и .

- Суммируем результаты всех возможных рекурсивных вызовов.

Функция кешируется с помощью lru_cache, чтобы ускорить вычисления за счет запоминания ранее вычисленных значений. Вызов f(25, 111) вернет количество всех допустимых программ.

# Импортируем кеширование для ускорения рекурсии
from functools import lru_cache

# Определяем рекурсивную функцию f(a, b, c1, c2)
# a - текущее число, b - целевое число
# c1 - предыдущая команда, c2 - команда два шага назад
@lru_cache(None)
def f(a, b, c1 = 0, c2 = 0):
    # Если текущее число больше целевого, путь невозможен
    if a > b:
        return 0
    # Если текущее число равно целевому, найден допустимый путь
    if a == b:
        return 1
    # Инициализируем счетчик программ на этом шаге
    s = 0
    # Определяем цифру единиц числа a
    x = a % 10
    # Определяем цифру десятков числа a
    y = a // 10 % 10

    # Команда 1: прибавить разряд единиц
    if c2 != 1 and x != 0:
        s += f(a + x, b, 1, c1)

    # Команда 2: прибавить разряд десятков
    if c2 != 2 and y != 0:
        s += f(a + y, b, 2, c1)

    # Команда 3: умножить на разряд единиц
    if c2 != 3 and x != 0 and x != 1:
        s += f(a * x, b, 3, c1)

    # Команда 4: умножить на разряд десятков
    if c2 != 4 and y != 0 and y != 1:
        s += f(a * y, b, 4, c1)

    # Команда 5: прибавить 1
    if c2 != 5:
        s += f(a + 1, b, 5, c1)

    # Возвращаем суммарное количество программ с этого шага
                                                                                                  
                                                                                                  
    return s

# Вычисляем и выводим количество программ от 25 до 111
print(f(25, 111))

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

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

1. Сначала мы определяем функцию f(a, b, c=0, r=False), где:

- — текущее число на экране,

- — целевое число,

- — номер команды, выполненной на предыдущем шаге (0, если команда еще не была использована),

- — логический флаг, который показывает, встречалось ли число 6 в траектории.

2. Внутри функции проверяем условия, которые запрещают продолжение программы:

- если текущее число стало больше или равно запрещённому числу 18, возвращаем 0, так как такие траектории не подходят;

- если текущее число совпадает с и флаг равен True (т.е. число 6 уже встречалось), возвращаем 1, так как найден корректный путь.

3. После этого проверяем, не достигли ли мы числа 6:

- если , устанавливаем , чтобы зафиксировать факт появления числа 6 в траектории.

4. Далее мы рекурсивно считаем количество программ, вызывая функцию для каждого возможного шага:

- вызов f(a * 2, b, 2, r) соответствует применению команды 2 "умножь на 2 мы фиксируем предыдущую команду как 2;

- вызов f(a * 3, b, 3, r) выполняется только если предыдущая команда не была 1 (команда "увеличь на 4"), что соответствует условию задачи;

- вызов f(a + 4, b, 1, r) выполняется только если предыдущая команда не была 2 (команда "умножь на 2").

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

6. В конце мы вызываем функцию с начальными значениями f(2, 296), чтобы получить ответ.

# Определяем функцию f(a, b, c=0, r=False), где
# a - текущее число, b - целевое число
# c - предыдущая команда, r - флаг наличия числа 6
def f(a, b, c = 0, r = False):
    # Если текущее число превысило целевое или равно запрещённому числу 18,
    # то путь невозможен, возвращаем 0
    if a > b or a == 18:
        return 0
    # Если текущее число совпадает с целевым и число 6 встречалось,
    # значит найден подходящий путь, возвращаем 1
    if a == b and r:
        return 1
    # Если текущее число равно 6, фиксируем факт его появления
    if a == 6:
        r = True

    # Применяем команду 2 "умножь на 2" всегда
    s = f(a * 2, b, 2, r)
    # Применяем команду 3 "умножь на 3", только если предыдущая команда не была 1
    if c != 1:
        s += f(a * 3, b, 3, r)
    # Применяем команду 1 "увеличь на 4", только если предыдущая команда не была 2
    if c != 2:
        s += f(a + 4, b, 1, r)
    # Возвращаем общее количество программ для текущего состояния
    return s

# Вызываем функцию от 2 до 296 и выводим результат
print(f(2, 296))

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

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

1. — текущее число на экране;

2. — целевое число;

3. — номер команды, выполненной на предыдущем шаге (по умолчанию , если это старт);

4. — флаг, указывающий, что число 21 уже встречено в траектории;

5. — флаг, указывающий, что число 68 уже встречено в траектории.

Логика работы функции:

1. Сначала проверяем, не превысило ли текущее число целевое .

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

2. Проверяем, совпадает ли текущее число с целевым, и встречены ли оба числа 21 и 68.

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

3. Обновляем флаги наличия чисел 21 и 68:

- Если , устанавливаем .

- Если , устанавливаем .

4. Далее определяем, какие команды можно выполнить на текущем шаге, учитывая правило смены команд:

- Если предыдущая команда была 1 или 3, разрешена только команда 2.

- Если предыдущая команда была 2, разрешены команды 1 и 3.

- Если это первый шаг (), разрешены все три команды.

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

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

Таким образом, при запуске функции f(1, 824) она рекурсивно переберет все возможные последовательности команд, учитывая ограничения на смену команд и наличие чисел 21 и 68 в траектории, и вернет общее количество корректных программ.

# Определяем рекурсивную функцию f(a, b, c=0, r1=False, r2=False)
# a — текущее число, b — целевое число
# c — номер предыдущей команды, r1 и r2 — флаги наличия чисел 21 и 68
def f(a, b, c = 0, r1 = False, r2 = False):
    # Если текущее число превысило целевое,
    # путь невозможен, возвращаем 0
    if a > b:
        return 0
    # Если достигли целевого числа и оба числа 21 и 68 уже встречены,
    # то путь корректен, возвращаем 1
    if a == b and r1 and r2:
        return 1
    # Обновляем флаги наличия чисел 21 и 68
    if a == 21:
        r1 = True
    if a == 68:
        r2 = True

    # Проверяем предыдущую команду и разрешенные следующие шаги
    if c == 1 or c == 3:
        # Если предыдущая команда 1 или 3, разрешена только команда 2
        return f(a + 3, b, 2, r1, r2)
    if c == 2:
        # Если предыдущая команда 2, разрешены команды 1 и 3
        return f(a + 1, b, 1, r1, r2) + f(a * 4, b, 3, r1, r2)

    # Если предыдущей команды не было, разрешены все три команды
    return f(a + 1, b, 1, r1, r2) + f(a + 3, b, 2, r1, r2) + f(a * 4, b, 3, r1, r2)

# Запускаем рекурсивную функцию от 1 до 824 и выводим количество корректных программ
print(f(1, 824))

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

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

1. – текущее число на экране;

2. – целевое число, к которому нужно прийти;

3. – количество последовательных применений команды 1 ("увеличь на 1");

4. – количество последовательных применений команды 2 ("умножь на 2").

Алгоритм функции состоит из следующих шагов:

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

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

3. В остальных случаях создаём переменную , которая будет накапливать количество успешных программ.

4. Если команда 1 применялась меньше трёх раз подряд (), то вызываем функцию рекурсивно с аргументами и добавляем результат к . Здесь мы увеличиваем на 1, увеличиваем счётчик , а счётчик обнуляем, так как сменили команду.

5. Если команда 2 применялась меньше трёх раз подряд (), вызываем функцию рекурсивно с аргументами и добавляем результат к . Здесь мы умножаем на 2, обнуляем , а увеличиваем на 1.

6. Возвращаем сумму , которая содержит количество всех программ из текущего состояния.

Вызов функции f(5, 299) даёт искомое количество программ, начинающихся с числа 5 и приводящих к числу 299 с учётом ограничения на повторение команд.

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

# Вызываем функцию с начальным числом 5 и целевым 299 и выводим результат
print(f(5, 299))