Автор: Арсений Обозненко
Введение
В соответствии со спецификацией ФИПИ, у 25-го задания высокий уровень сложности. На его решение отведено 20 минут. Учитывая совсем небольшой объём кода, такие рамки обусловлены переборной сутью алгоритма.
Оценка сложности и подбор оптимального метода решения позволят решать задачи намного быстрее.
Применение fnmatch
В заданиях под маской подразумевается шаблон, проверяющий строки.
В Python проверка уже реализована в модулеfnmatch. Одноимённая функция fnmatch принимает строку и маску, после чего возвращает булево значение, указывающее, соответствует ли строка заданному шаблону.
from fnmatch import fnmatch
mask = 'i_love_yandex'
print(fnmatch('i_love_yandex', mask)) # True
print(fnmatch('i_love_pelmenies', mask)) # False
print(fnmatch('they_and_i_love_yandex', mask)) # False
В маске можно задавать один произвольный символ с помощью вопросительного знака (?).
from fnmatch import fnmatch
mask = 'i_love_yand?x'
print(fnmatch('i_love_yandex', mask)) # True
print(fnmatch('i_love_yandux', mask)) # True
print(fnmatch('i_love_yandeeex', mask)) # False
Звёздочка (*) помогает задать любое количество произвольных символов (даже 0).
from fnmatch import fnmatch
mask = 'i_love_yand*'
print(fnmatch('i_love_yandex', mask)) # True
print(fnmatch('i_love_yanduuuuuuuuuuux', mask)) # True
print(fnmatch('i_love_yand', mask)) # True
Задача 1: демоверсия ФИПИ (2025)
Решим задачу с помощью fnmatch. Удобно, что шаблон-маска записывается абсолютно так же, как в задании.
Проверка строк на совпадение с маской занимает больше времени, чем проверка арифметических выражений с числами. Поэтому сначала проверим делимость и только после этого используем fnmatch.
from fnmatch import fnmatch
mask = '3?12?14*5'
for n in range(1, 10**10):
if n % 1917 == 0:
if fnmatch(str(n), mask):
print(n, n // 1917)
Программа написана верно и выдаёт правильные ответы, но делает это непростительно долго.
Миллиард — разумное ограничение перебора чисел для Python. В задаче перебирается 10 миллиардов чисел, что вынуждает искать пути оптимизации.
Оптимизация проверки на делимость
Возьмём число, заведомо делящееся на 1917. В случае натуральных чисел 1917 и будет первым подходящим. Но удобнее использовать 0, т. к. он делится на любое натуральное число. Будем брать не каждое следующее за нулём число, а с шагом в 1917. Таким образом, можно убрать проверку на делимость, ведь мы перебираем заведомо подходящие числа.
from fnmatch import fnmatch
mask = '3?12?14*5'
for n in range(0, 10**10, 1917):
if fnmatch(str(n), mask):
print(n, n // 1917)
Решили задачу за 10 секунд, так как перебор сократился в 1917 раз.
Задача 2: fnmatch не спасает
Задача отличается от предыдущей условием делимости. При делении 0 на 123 остаток будет равен 0, а должен быть 42. Сдвинем начальную точку отсчёта до 42, а шаг оставим 123 — таким образом, мы будем перебирать числа вида 123 × n + 42, где n — целое неотрицательное число.
from fnmatch import fnmatch
mask = '4?8?15?16?23'
for n in range(42, 10**12, 123):
if fnmatch(str(n), mask):
print(n, n // 123)
Программа работает слишком долго. Без шага 123 цикл бы выполнялся триллион раз, а с ним — чуть меньше 10 миллиардов, что тоже много. Необходимо ещё сократить количество вариантов.
Оптимизация перебора
Внимательно рассмотрим маску 4?8?15?16?23. Вней содержится 8 цифр и 4 вопросительных знака, которые означают ровно одну произвольную цифру. Будем перебирать все возможные комбинации этих цифр и составлять число, которое заведомо подходит под маску. После этого останется только проверить, что при делении на 123 остаток будет равен 42.
На каждой позиции вопросительного знака стоит одна цифра от 0 до 9, поэтому нам понадобится 4 вложенных цикла для перебора всех комбинаций. Количество вариантов: 10 × 10 × 10 × 10 = 10 000, такой алгоритм выполнится быстро. Обратите внимание, что если бы вопросительный знак стоял на первой позиции в числе, то на его место нельзя было бы поставить 0, т. к. число не может начинаться с 0.
Сгенерируем все эти варианты как f-строки, проверим остаток от деления на 123. Если число подходит, добавим его в массив. По условию нам необходимо найти количество подходящих чисел и максимальное из них. Значит, остаётся вычислить длину массива (количество подходящих чисел) и максимальный элемент в нём.
# Массив для подходящих чисел
m = []
# Возможные цифры на месте "?"
digits = '0123456789'
for d1 in digits:
for d2 in digits:
for d3 in digits:
for d4 in digits:
# Формируем f-строку
n = f'4{d1}8{d2}15{d3}16{d4}23'
# Переводим в целое число
n = int(n)
# Проверяем остаток от деления
if n%123 == 42:
# Добавляем в массив
m.append(n)
# Выводим длину массива и максимальный элемент в нём
print(len(m), max(m))
#85 498915816123
Ответ: 85 498915816123
Задача 3: перебор звёздочек
На месте звёздочки может стоять последовательность цифр произвольной длины, в том числе и пустая последовательность. Число не должно превышать $10^{10}$ — единица и десять нулей. Поскольку маска начинается на цифру 4, а 4 > 1, подходящее число состоит максимум из 10 цифр. Следовательно, суммарно на местах двух звёздочек может находиться максимум 5 цифр.
Перебирать различные сочетания цифр будем с помощью функции product из модуля itertools. Подробнее о том, как она работает, можно узнать в одной из предыдущих статей.
Алгоритм перебора последовательностей цифр на месте звёздочки:
from itertools import product
# Цикл для возможной длины последовательности на месте звёздочки
for len_star_1 in range(6):
# Создаём все возможные последовательности цифр длины len_star_1
for x in product('0123456789', repeat=len_star_1):
# Переводим кортеж в строку
a = ''.join(x)
В нашей маске две звёздочки, поэтому понадобится два цикла для перебора их длин и столько же для создания каждой из последовательностей. Перед тем как их формировать, проверяем, что суммарная длина не превышает 5.
from itertools import product
m = []
for len_star_1 in range(6):
for len_star_2 in range(6):
if (len_star_1 + len_star_2) <= 5:
for x in product('0123456789', repeat=len_star_1):
for y in product('0123456789', repeat=len_star_2):
# Формируем строку
n = '48'+''.join(x) + '15' + ''.join(y) + '0'
# Переводим в целое число
n = int(n)
# Если n делится на 42, добавляем его в массив, а также добавляем результат деления на 42
if n%42 == 0:
m.append([n, n//42])
# Сортируем массив по убыванию
m = sorted(m, reverse=True)
# Выводим первые 5 наибольших чисел и их результаты деления
print(m[:5])
Этот алгоритм перебирает примерно 420 тысяч различных чисел n, что значительно меньше $10^{10}$.
Итоги
- Используйте
fnmatchдля проверки по шаблону — это удобно, если маска в задании дана в том же формате - Оптимизируйте перебор:
- если нужно проверять делимость, перебирайте числа с шагом, равным делителю (или с учётом остатка)
- если в маске есть «?», перебирайте все комбинации цифр на этих позициях — это значительно быстрее полного перебора
- если в маске есть «*», оцените максимальную длину и перебирайте все возможные строки для «*» с помощью
itertools.product
- Сначала проверяйте арифметические условия, потом маску. Это может ускорить работу, если условие на делимость отсекает много вариантов
Оттачивайте свои навыки, решая подборку задач.