Как fnmatch понимает маску

Маска в задании 25 состоит из цифр и символов ? и *. Функция fnmatch из стандартного модуля fnmatch понимает эти символы так же: ? — ровно один любой символ, * — любая последовательность символов, в том числе пустая. Поэтому маску из условия можно переписать в программу без изменений.

fnmatch сравнивает строки, поэтому число сначала переводят в строку: fnmatch(str(n), '3?12?14*5'). В записи числа только цифры, так что «любой символ» здесь означает «любая цифра».

  • 3212614035 подходит: вместо ? стоят 2 и 6, вместо * — 03.
  • 32126145 тоже подходит: * заменена пустой последовательностью.

В стандартной библиотеке C++ такой функции нет. Её пишут сами: короткая рекурсивная функция matches сравнивает строку с маской символ за символом, а на * пробует два варианта — звёздочка пустая или забирает ещё один символ. Она есть во вкладке C++ у программ ниже.

Перебор кратных

Нужно найти на отрезке [A; B] числа по маске 3?12?14*5, которые делятся на 1917. Отрезок длиной до миллиарда целиком перебирать долго. Если идти шагом 1917 от первого кратного, проверок станет в 1917 раз меньше: около полумиллиона.

Перебор кратных
from fnmatch import fnmatch

a, b = map(int, input().split())
# Первое кратное 1917, которое не меньше a, — деление с округлением вверх.
first = (a + 1916) // 1917 * 1917
# Идём шагом 1917: так проверяются только числа, которые делятся на 1917.
for n in range(first, b + 1, 1917):
    # fnmatch сравнивает строку с маской: ? — ровно один символ,
    # * — любая последовательность символов, в том числе пустая.
    if fnmatch(str(n), '3?12?14*5'):
        print(n, n // 1917)
#include <iostream>
#include <string>
using namespace std;

// Подходит ли строка s, начиная с позиции i, под маску, начиная с позиции j.
// ? — ровно один символ, * — любая последовательность символов, в том числе пустая.
bool matches(const string& s, const string& mask, size_t i = 0, size_t j = 0) {
    if (j == mask.size())
        return i == s.size();
    if (mask[j] == '*')
        // Звёздочка либо пустая, либо забирает ещё один символ строки.
        return matches(s, mask, i, j + 1) || (i < s.size() && matches(s, mask, i + 1, j));
    return i < s.size() && (mask[j] == '?' || mask[j] == s[i]) && matches(s, mask, i + 1, j + 1);
}

int main() {
    long long a, b;
    cin >> a >> b;
    // Первое кратное 1917, которое не меньше a, — деление с округлением вверх.
    long long first = (a + 1916) / 1917 * 1917;
    // Идём шагом 1917: так проверяются только числа, которые делятся на 1917.
    for (long long n = first; n <= b; n += 1917) {
        if (matches(to_string(n), "3?12?14*5"))
            cout << n << ' ' << n / 1917 << '\n';
    }
}

fnmatch работает медленнее, чем сравнение отдельных цифр вручную. Но при полумиллионе проверок программа укладывается в лимит, а маску из условия можно передать как есть: ? и * не приходится переводить в ручные проверки длины. В C++ своя функция matches работает быстро, так что о времени здесь можно не думать.

Маска делителя

Иногда под маску должно подходить не само число, а его делитель. Тогда делители перебирают парами до квадратного корня, а fnmatch проверяет каждый делитель из пары.

Маска делителя
from fnmatch import fnmatch


def best_divisor(n):
    # Делители идут парами d и n // d, где d не больше корня из n.
    # Каждый из пары сверяем с маской и запоминаем наименьший подходящий.
    best = 0
    for d in range(1, int(n ** 0.5) + 1):
        if n % d == 0:
            for v in (d, n // d):
                if fnmatch(str(v), '3*2?') and (best == 0 or v < best):
                    best = v
    return best


a = int(input())
n = a + 1
found = 0
# Перебираем числа больше a по возрастанию, пока не найдём пять подходящих.
while found < 5:
    best = best_divisor(n)
    if best > 0:
        print(n, best)
        found += 1
    n += 1
#include <iostream>
#include <string>
using namespace std;

// Та же проверка маски, что в предыдущей программе: ? — один символ, * — любые символы.
bool matches(const string& s, const string& mask, size_t i = 0, size_t j = 0) {
    if (j == mask.size())
        return i == s.size();
    if (mask[j] == '*')
        return matches(s, mask, i, j + 1) || (i < s.size() && matches(s, mask, i + 1, j));
    return i < s.size() && (mask[j] == '?' || mask[j] == s[i]) && matches(s, mask, i + 1, j + 1);
}

long long best_divisor(long long n) {
    // Делители идут парами d и n / d, где d не больше корня из n.
    // Каждый из пары сверяем с маской и запоминаем наименьший подходящий.
    long long best = 0;
    for (long long d = 1; d * d <= n; d++) {
        if (n % d == 0) {
            for (long long v : {d, n / d}) {
                if (matches(to_string(v), "3*2?") && (best == 0 || v < best))
                    best = v;
            }
        }
    }
    return best;
}

int main() {
    long long a;
    cin >> a;
    int found = 0;
    // Перебираем числа больше a по возрастанию, пока не найдём пять подходящих.
    for (long long n = a + 1; found < 5; n++) {
        long long best = best_divisor(n);
        if (best > 0) {
            cout << n << ' ' << best << '\n';
            found += 1;
        }
    }
}

Когда перебор слишком долгий

Возьмём маску 4*8?, числа, кратные 37, и отрезок до 9 999 999 999. Кратных 37 на таком отрезке около 270 миллионов. Миллион проверок fnmatch занимает около двух секунд, значит, весь перебор займёт около 9 минут.

В этой задаче цифры числа не должны повторяться, и это условие сильнее делимости. Поэтому числа не перебирают, а строят по маске: вместо * и ? подставляют только ещё не использованные цифры и проверяют делимость у полученных чисел. Таких чисел около 110 тысяч, и программа работает доли секунды.

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

  • Число вместо строки. fnmatch(n, '4*8?') завершится ошибкой: функция принимает только строки. Нужно str(n), в C++ — to_string(n).
  • Забытая пустая *. Под маску 3?12?14*5 подходит и восьмизначное 32126145. fnmatch учитывает это сам, а ручная проверка вида len(s) > 8 такое число потеряет.
  • Перебор без шага. Если число должно делиться на d, начинайте с первого кратного d и идите шагом d. Перебор всех чисел подряд с проверкой n % d == 0 в d раз дольше.