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

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

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

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

Две обязательные точки разбивают программу на три части: A → C, C → D и D → B. Команды увеличивают число, а C меньше D, поэтому любая программа, посетившая обе точки, посещает их именно в этом порядке. Число программ равно произведению количества способов для трёх частей. Для одной части ways(x, goal) возвращает 1 на цели, 0 за целью и сумму ways(x + 1, goal) + ways(2 × x, goal) до неё. Важно ограничивать каждую часть её собственной целью: перескочив контрольную точку, вернуться к ней уже нельзя.

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

Ввод

1 4 2 3

Вывод

2
Разбор примера по шагам
Состояние или программаКак считаем
1 → 22 способа
2 → 31 способ
3 → 41 способ
вся программа2 × 1 × 1 = 2

Для 1 → 2 → 3 → 4 получаем 2 × 1 × 1 = 2 программы: AAA и BAA. Во втором примере 2 → 3 возможно только прибавлением, 3 → 6 — тремя прибавлениями или умножением, 6 → 8 — двумя прибавлениями. Ответ 2.

Код на Python и C++

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

from functools import lru_cache

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

@lru_cache(None)
def ways(x, goal):
    if x == goal:
        return 1
    if x > goal:
        return 0
    return ways(x + 1, goal) + ways(x * 2, goal)

print(ways(a, c) * ways(c, d) * ways(d, b))
#include <iostream>
#include <functional>
#include <cstring>
using namespace std;

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

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

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

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

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

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

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

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