Что спрашивают
Нужно найти на отрезке [A; B] числа по маске 4*8?, делящиеся на 37 и состоящие из разных цифр. Звёздочка может быть пустой, вопросительный знак заменяет одну цифру. Границы включены.
Во всей записи, включая фиксированные цифры 4 и 8, повторений быть не должно. B не больше 9 999 999 999; подходящее число на отрезке существует.
Приём решения
Сразу исключим цифры 4 и 8 из свободных позиций: они уже использованы в маске. Остаются 01235679. Их подстановки должны быть без повторений, поэтому подходят перестановки permutations.
- Переберите полную длину записи от трёх до количества цифр B, но не больше десяти.
- Выберите упорядоченные различные цифры для всех свободных позиций; их на две меньше полной длины.
- Последняя выбранная цифра идёт в ?, а остальные — в *.
- Соберите запись
4 + звёздочка + 8 + вопросительный знак, проверьте отрезок и делимость. - Отсортируйте найденные пары «число, частное».
При длине три свободная цифра всего одна, и замена звёздочки получается пустой. При длине десять используются все десять цифр по одному разу. Всего для полной области достаточно 109 600 подстановок; генератор перестановок не хранит их все одновременно.
Уникальность не приходится проверять после построения: разные свободные цифры обеспечены permutations, а фиксированные 4 и 8 заранее удалены. Сохраняются только найденные ответы. Если ограничение другое, можно сначала построить запись и затем проверить её свойство, но здесь выгоднее учесть запрет уже в генерации.
Разбор на примере
Ввод
480 5000
Вывод
481 13
| Кандидат | Маска и делимость | Разные цифры | Итог |
|---|---|---|---|
| 481 | Подходит: 37 × 13 | Да | Выводим |
| 4181 | Подходит: 37 × 113 | Нет: две 1 | Исключаем |
| 4588 | Подходит: 37 × 124 | Нет: две 8 | Исключаем |
| 4884 | Подходит: 37 × 132 | Нет: повторяются 4 и 8 | Исключаем |
Число 481 использует пустую звёздочку и цифру 1 в вопросительном знаке. Оно даёт единственную строку ответа на выбранном отрезке. Остальные приведённые кандидаты удовлетворяют маске и делимости, но нарушают условие различия цифр.
Код на Python и C++
Свободные позиции не получают цифры 4 или 8. В начале звёздочки может стоять 0: это внутренняя позиция числа, вся запись начинается с 4.
В C++ нет готового перебора перестановок части набора: next_permutation переставляет набор целиком. Цифры подставляет рекурсивная функция build: она берёт ещё не использованную цифру, вызывает себя для следующей позиции и возвращает цифру обратно. Числа больше 231, поэтому тип — long long.
import sys
from itertools import permutations
def solve(a, b):
available = '01235679'
rows = []
for length in range(3, min(10, len(str(b))) + 1):
for free in permutations(available, length - 2):
text = '4' + ''.join(free[:-1]) + '8' + free[-1]
n = int(text)
if a <= n <= b and n % 37 == 0:
rows.append((n, n // 37))
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>
<string>
<utility>
<vector>
using namespace std;
const string available = "01235679";
vector<pair<long long, long long>> rows;
long long a, b;
// Дописывает к free ещё left разных цифр из available всеми способами.
void build(string& free, vector<bool>& used, int left) {
if (left == 0) {
string text = "4" + free.substr(0, free.size() - 1) + "8" + free.back();
long long n = stoll(text);
if (a <= n && n <= b && n % 37 == 0)
rows.push_back({n, n / 37});
return;
}
for (size_t i = 0; i < available.size(); i++) {
if (used[i])
continue;
used[i] = true;
free.push_back(available[i]);
build(free, used, left - 1);
free.pop_back();
used[i] = false;
}
}
int main() {
cin >> a >> b;
int max_length = min<int>(10, to_string(b).size());
for (int length = 3; length <= max_length; length++) {
string free;
vector<bool> used(available.size(), false);
build(free, used, length - 2);
}
sort(rows.begin(), rows.end());
for (auto [n, q] : rows)
cout << n << ' ' << q << '\n';
}
Типичные ошибки
- Проверять повторения только в звёздочке
Повтор может возникнуть между свободной и фиксированной позицией. Учитывается вся запись числа.
- Запретить пустую звёздочку
Трёхзначные числа вида 48? разрешены. Перебор полной длины начинается с трёх.
- Перебирать повторения, а потом забыть их отсеять
product и permutations решают разные задачи. Для разных цифр используйте перестановки без повторений или явную проверку множества.