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

На включённом отрезке [A; B] найдите числа, соответствующие маске 3?12?14*5 и делящиеся на 1917. Знак ? заменяет ровно одну цифру, а * — любую последовательность цифр, включая пустую.

Нужно вывести числа по возрастанию и их частные от деления на 1917. По условию B не больше 10^10, ширина отрезка не больше 10^9 и хотя бы одно подходящее число существует.

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

Вместо перебора всех чисел отрезка построим только записи, соответствующие маске. Без звёздочки в ней восемь цифр. Запись начинается с 3, поэтому одиннадцатизначный вариант уже больше 10^10. Значит, звёздочка содержит ноль, одну или две цифры.

  1. Переберите длину замены звёздочки от нуля до двух.
  2. Подставьте по одной цифре в каждый вопросительный знак.
  3. Для звёздочки переберите все последовательности нужной длины, включая начинающиеся с нуля.
  4. Проверьте границы A <= n <= B и остаток n % 1917 == 0.
  5. Отсортируйте найденные пары перед выводом.

Всего получается 10 × 10 × (1 + 10 + 100) = 11 100 записей. Это ограничение зависит от маски и максимального числа цифр, а не от ширины отрезка. Длины замен и позиции вопросительных знаков однозначно определяют запись, поэтому дубликаты не возникают.

Для цифр звёздочки используем product: пустое произведение даёт одну пустую подстановку, а последовательность ('0', '3') сохраняет обе позиции. Преобразование всей записи в int безопасно: её первая цифра всегда 3.

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

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

Ввод

351261490 351261500

Вывод

351261495 183235
Разбор примера по шагам
Часть записиПодстановкаРезультат
Первый ?535…
Второй ?63512614…
Звёздочка9351261495
Деление на 1917Без остатка183235

В пределах узкого отрезка подходит 351261495. Его запись получается заменами ? на 5 и 6, а * на 9. Частное равно 183235. Ноль в начале замены звёздочки также допустим: например, подстановка 03 означает именно две цифры, а не одну цифру 3.

Код на Python и C++

Граница длины звёздочки здесь выведена для конкретной маски и B ≤ 10^10. При изменении маски число подстановок нужно оценивать заново.

В C++ вместо product — вложенные циклы, а число собирается арифметикой: начало 3x12y14 умножается на 10w, к нему прибавляется хвост из w цифр, затем приписывается пятёрка. Числа больше 231, поэтому тип — long long.

import sys
from itertools import product


def solve(a, b):
    digits = '0123456789'
    rows = []
    for width in range(3):
        for x, y in product(digits, repeat=2):
            for tail in product(digits, repeat=width):
                text = '3' + x + '12' + y + '14' + ''.join(tail) + '5'
                n = int(text)
                if a <= n <= b and n % 1917 == 0:
                    rows.append((n, n // 1917))
    return sorted(rows)

if __name__ == '__main__':
    a, b = map(int, sys.stdin.read().split())
    rows = solve(a, b)
    for row in rows:
        print(*row)
#include <algorithm>
#include <iostream>
#include <utility>
#include <vector>
using namespace std;

vector<pair<long long, long long>> solve(long long a, long long b) {
    vector<pair<long long, long long>> rows;
    long long power = 1;
    for (int width = 0; width < 3; width++) {
        for (int x = 0; x <= 9; x++) {
            for (int y = 0; y <= 9; y++) {
                long long head = 3'000'000 + x * 100'000 + 12'000 + y * 100 + 14;
                for (long long tail = 0; tail < power; tail++) {
                    long long n = (head * power + tail) * 10 + 5;
                    if (a <= n && n <= b && n % 1917 == 0)
                        rows.push_back({n, n / 1917});
                }
            }
        }
        power *= 10;
    }
    sort(rows.begin(), rows.end());
    return rows;
}

int main() {
    long long a, b;
    cin >> a >> b;
    for (auto [n, q] : solve(a, b))
        cout << n << ' ' << q << '\n';
}

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

  • Дать вопросительному знаку несколько цифр

    Каждый ? занимает ровно одну позицию. Произвольная длина разрешена только для *.

  • Потерять ноль в начале замены звёздочки

    Звёздочка — фрагмент записи, а не отдельное натуральное число. Подстановка 03 должна остаться двухзначной.

  • Исключить концы отрезка

    Обе границы входят в поиск. Используйте нестрогие сравнения с A и B.

  • Считать порядок генерации порядком чисел

    После разных подстановок записи получаются не обязательно по возрастанию. Отсортируйте результат.