Что спрашивают
На включённом отрезке [A; B] найдите числа, соответствующие маске 3?12?14*5 и делящиеся на 1917. Знак ? заменяет ровно одну цифру, а * — любую последовательность цифр, включая пустую.
Нужно вывести числа по возрастанию и их частные от деления на 1917. По условию B не больше 10^10, ширина отрезка не больше 10^9 и хотя бы одно подходящее число существует.
Приём решения
Вместо перебора всех чисел отрезка построим только записи, соответствующие маске. Без звёздочки в ней восемь цифр. Запись начинается с 3, поэтому одиннадцатизначный вариант уже больше 10^10. Значит, звёздочка содержит ноль, одну или две цифры.
- Переберите длину замены звёздочки от нуля до двух.
- Подставьте по одной цифре в каждый вопросительный знак.
- Для звёздочки переберите все последовательности нужной длины, включая начинающиеся с нуля.
- Проверьте границы
A <= n <= Bи остатокn % 1917 == 0. - Отсортируйте найденные пары перед выводом.
Всего получается 10 × 10 × (1 + 10 + 100) = 11 100 записей. Это ограничение зависит от маски и максимального числа цифр, а не от ширины отрезка. Длины замен и позиции вопросительных знаков однозначно определяют запись, поэтому дубликаты не возникают.
Для цифр звёздочки используем product: пустое произведение даёт одну пустую подстановку, а последовательность ('0', '3') сохраняет обе позиции. Преобразование всей записи в int безопасно: её первая цифра всегда 3.
Другой подход — проверять кратные 1917 с помощью fnmatchcase. Он тоже исключает большинство чисел, но в этой фиксированной маске прямое построение кандидатов даёт короткий ограниченный перебор.
Разбор на примере
Ввод
351261490 351261500
Вывод
351261495 183235
| Часть записи | Подстановка | Результат |
|---|---|---|
| Первый ? | 5 | 35… |
| Второй ? | 6 | 3512614… |
| Звёздочка | 9 | 351261495 |
| Деление на 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)
<algorithm>
<iostream>
<utility>
<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.
- Считать порядок генерации порядком чисел
После разных подстановок записи получаются не обязательно по возрастанию. Отсортируйте результат.