Как 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)
<iostream>
<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
<iostream>
<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 раз дольше.