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

Нужно найти на отрезке [A; B] числа по маске 4*8?, делящиеся на 37 и состоящие из разных цифр. Звёздочка может быть пустой, вопросительный знак заменяет одну цифру. Границы включены.

Во всей записи, включая фиксированные цифры 4 и 8, повторений быть не должно. B не больше 9 999 999 999; подходящее число на отрезке существует.

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

Сразу исключим цифры 4 и 8 из свободных позиций: они уже использованы в маске. Остаются 01235679. Их подстановки должны быть без повторений, поэтому подходят перестановки permutations.

  1. Переберите полную длину записи от трёх до количества цифр B, но не больше десяти.
  2. Выберите упорядоченные различные цифры для всех свободных позиций; их на две меньше полной длины.
  3. Последняя выбранная цифра идёт в ?, а остальные — в *.
  4. Соберите запись 4 + звёздочка + 8 + вопросительный знак, проверьте отрезок и делимость.
  5. Отсортируйте найденные пары «число, частное».

При длине три свободная цифра всего одна, и замена звёздочки получается пустой. При длине десять используются все десять цифр по одному разу. Всего для полной области достаточно 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)
#include <algorithm>
#include <iostream>
#include <string>
#include <utility>
#include <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 решают разные задачи. Для разных цифр используйте перестановки без повторений или явную проверку множества.