Что спрашивают

A вычитает 1. B делит на 2, только если число чётное. Найдите число программ, переводящих A в B. Пустая программа допустима и считается одной программой, если начальное число уже равно конечному и остальные ограничения выполнены. Разные последовательности команд считаются разными программами, даже если дают одинаковую траекторию.

Два целых числа A и B: 1 ≤ B ≤ A ≤ 100. На сайте параметры читаются из ввода; на экзамене их берут из условия.

Приём решения

Обе команды уменьшают число, поэтому меняется направление проверки границы. Пусть f(x) — число программ из x до B. На цели возвращаем 1, а при x < B — 0. Команда A даёт f(x − 1). Если x чётное, добавляем f(x / 2); для нечётного деление запрещено. Проверка чётности обязательна: целочисленное деление нечётного x описывало бы другую команду. Разные команды учитываются отдельно, даже когда из 2 обе дают 1. Сохранение значений f(x) избавляет от повторного подсчёта одинаковых продолжений.

Разбор на примере

Ввод

4 1

Вывод

4
Разбор примера по шагам
Состояние или программаКак считаем
11 пустая программа
2f(1) + f(1) = 2
3f(2) = 2
4f(3) + f(2) = 4

Из 4 в 1 подходят AAA, AAB, BA и BB: четыре программы. В точке 2 обе команды приводят к 1, но записи программ различны. Из 7 в 2 можно идти только через 6, а затем либо 6 → 5 → 4, либо 6 → 3; суммарно три программы.

Код на Python и C++

Функция возвращает количество продолжений, а не длину программы. Python запоминает значения через lru_cache, C++ — через таблицу с начальным значением −1. Число 0 в таблице уже является вычисленным ответом. Все ответы при данных ограничениях помещаются в знаковое 64-битное целое.

from functools import lru_cache

a, b = map(int, input().split())

@lru_cache(None)
def ways(x):
    if x == b:
        return 1
    if x < b:
        return 0
    result = ways(x - 1)
    if x % 2 == 0:
        result += ways(x // 2)
    return result

print(ways(a))
#include <iostream>
#include <functional>
#include <cstring>
using namespace std;

int main() {
    int a, b;
    cin >> a >> b;
    static long long memo[101][1];
    memset(memo, -1, sizeof(memo));
    function<long long(int)> ways = [&](int x) -> long long {
        if (x == b) return 1;
        if (x < b) return 0;
        auto &result = memo[x][0];
        if (result != -1) return result;
        result = ways(x - 1);
        if (x % 2 == 0) result += ways(x / 2);
        return result;
    };
    cout << ways(a) << "\n";
}

Типичные ошибки

  • Неверный ответ на цели

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

  • Потеря одной из команд

    Складывайте ответы для разных допустимых первых команд. Если команды приводят к одному числу, они всё равно задают разные записи программ.

  • Недостаточное состояние

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