Маски в задании №25

На реальном экзамене по информатике в 2022 году были представлены 25-е задачи на маски. С тех пор они очень популярны и востребованы. В этой статье разберём способы решения простых и не очень задачек с масками.

Строки и срезы

Одним из способов решения задач является использование строк и срезов. Рассмотрим его на примере какой-нибудь постановки формата ЕГЭ.

Задача №7095 (kompege):
«Назовём маской числа последовательность цифр, в которой также могут встречаться следующие символы:

– символ «?» означает ровно одну произвольную цифру;
– символ «*» означает любую последовательность цифр произвольной длины; в том числе «*» может задавать и пустую последовательность.
Например, маске 123*4?5 соответствуют числа 123405 и 12300405.

Среди натуральных чисел, не превышающих 10^8, найдите все числа, соответствующие маске 1234*54, делящиеся на 21 без остатка. В ответе запишите в первом столбце таблицы все найденные числа в порядке возрастания, а во втором столбце – соответствующие им результаты деления этих чисел на 21».

Решение:
Для решения задачи мы переберем числа из отрезка [0; 10^8]. Диапазон немалый, потому мы оптимизируем перебор, опираясь на факт о том, что искомые числа делятся на 21 без остатка - это дает нам возможность использовать шаг перебора, равный 21, ведь если мы начнем с числа, кратного 21 (с нуля, например), тогда каждое последующее число, кратное 21, будет встречаться ровно через 21. Каждое из чисел мы проверим на соответствие маске, для чего переведем int в str и с помощью срезов проверим, точно ли первые 4 символа = «1234», а последние 2 = «54», и если да, значит, нас уже не интересует, что располагается между ними на месте «*» - будь это число или ничего.

Получим следующий код решения задачи:

Ответ:
1234254 58774
12341154 587674
12343254 587774
12345354 587874
12347454 587974
12349554 588074.

Использование функции fnmatch

Популярным в наше время способом решения задач на маски является использование функции fnmatch из модуля fnmatch.

На вход она принимает два аргумента - filename и pattern. И проверяет соответствие строки filename шаблону pattern. Таким образом:

fnmatch('123', '1?3') вернёт True

fnmatch('1245', '???6') вернёт False

Решим задачку формата ЕГЭ с помощью fnmatch.

Задача №7273 (kompege):
«Назовём маской числа последовательность цифр, в которой также могут встречаться следующие символы:

– символ «?» означает ровно одну произвольную цифру;
– символ «*» означает любую последовательность цифр произвольной длины; в том числе «*» может задавать и пустую последовательность.
Например, маске 123*4?5 соответствуют числа 123405 и 12300405.

Среди натуральных чисел, не превышающих 10^9, найдите все числа, соответствующие маске 12345?7?8, делящиеся на число 23 без остатка.
В ответе запишите в первом столбце таблицы все найденные числа в порядке возрастания, а во втором столбце – соответствующие им результаты деления этих чисел на 23».

Решение:
Для решения задачи мы, как и в прошлый раз, переберём числа из отрезка [0; 10^9], и тоже с шагом для оптимизации - на сей раз он = 23. Каждое из чисел мы будем переводить в тип str и проверять на соответствие данной нам маске с помощью fnmatch, который прежде импортируем из fnmatch.

Получим следующий код решения задачи:

Ответ:
123450798 5367426
123451718 5367466
123453788 5367556
123454708 5367596
123456778 5367686
123459768 5367816.

Перебор и генерация масок

У описанных выше способов есть свои минусы: что, если количество рассматриваемых чисел будет слишком велико? Вдруг придется перебирать числа из, например, отрезка [0; 10^12]? Тогда мы не получим ответ за разумное время - нам не поможет даже шаг. На помощь здесь приходит перебор, но только не чисел, а тех элементов, которые могут стоять на месте «?» и «*» в масках. Снова рассмотрим на примере задачи - теперь уже не столь простой.

Задача №7321 (kompege):
«Назовём маской числа последовательность цифр, в которой также могут встречаться следующие символы:

— символ «?» означает ровно одну произвольную цифру;
— символ «*» означает любую последовательность цифр произвольной длины; в том числе «*» может задавать и пустую последовательность.
Например, маске 123*4?5 соответствуют числа 123405 и 12300405.

Найдите все натуральные числа, не превышающие 10^12, которые соответствуют маске 403020?10* и при этом без остатка делятся на 603. В ответе запишите все четные найденные числа в порядке возрастания, справа от каждого запишите частное от его деления на 603».

Решение:
Мы видим, что в искомом числе недостает двух элементов: цифры, стоящей на месте «?» и числа (возможно), стоящего на месте «*». Разобьём решение задачи на этапы - сначала найдем все варианты, где на месте «*» ничего не стоит, затем варианты, когда на месте «*» стоит один, два или три знака (причем понимаем, что 3 знака - максимум, ведь иначе число превысит 10^12).

1) На месте «*» ничего не стоит - генерируем цифры, стоящие на «?»:

2) На месте «*» стоит одна цифра - генерируем для каждого варианта «?» еще все возможные варианты цифр под «*»:

3) На месте «*» стоят две цифры - здесь нам придется дополнить однозначные числа нулями слева (чтобы, например, «2» преобразовалось в «02») - для этого мы воспользуемся f-строками. Например, f'{5:02}' вернет '05'. Получаем:

4) Или если на месте «*» стоят три цифры:

Весь код будет выглядеть так:

Конечно, его можно сократить. Для этого мы отдельно проверим и случай, когда на месте «*» не стоит ничего, и все остальные случаи, когда на месте «*» стоит от одной до трёх цифр. Для этого мы переберем количество нулей, до которого будем дополнять «*» (от 0 до 3). И рассмотрим все возможные варианты «*»: и одноразрядное число (с дополнением нулями до длины = 0, 1, 2 и 3 соответственно), и двухразрядное, и трехразрядное тоже:

Правда, это вряд ли это упрощение имеет смысл, ведь первый вариант куда легче как для понимания, так и для отладки. Выбирать только вам, в любом случае.

Ответ:
403020010278 668358226
403020110376 668358392
403020210474 668358558
403020310572 668358724
403020410670 668358890
403020510768 668359056
403020610866 668359222
403020710964 668359388.

Давайте решим ещё одну задачку для закрепления темы с перебором.

Задача №7322 (kompege):
«Назовём маской числа последовательность цифр, в которой также могут встречаться следующие символы:

— символ «?» означает ровно одну произвольную цифру;
— символ «*» означает любую последовательность цифр произвольной длины; в том числе «*» может задавать и пустую последовательность.
Например, маске 123*4?5 соответствуют числа 123405 и 12300405.

Найдите все натуральные числа, не превышающие 10^12, которые соответствуют маске 4253*64* и при этом без остатка делятся на 503. В ответе запишите те из найденных чисел, в которых сумма числовых значений, стоящих на месте звездочек, кратна 503. В случае, если на месте звездочки пустая строка, считать значение 0. Числа приведите в порядке возрастания, справа от каждого числа выведите сумму разрядов для частного от деления найденного числа на 503».

Решение:
Мы переберём все числа, которые могут стоять на месте первой «*» - они могут быть максимум шестиразрядными (чтобы итоговое число не превышало 10^12), а для каждого из них все возможные числа, которые могут стоять на месте второй «*». Причем разрядность числа, стоящего на месте второй «*», зависит от разрядности первого числа, ибо в сумме количество их разрядов не должно превышать 6. Рассматривать будем только те числа, которые делятся на 503, при этом сумма чисел, стоящих на месте «*», тоже должна делиться на 503 (чего требуют в условии).

Получим следующий код:

Ответ:
425330964194 845588398
425330964697 845588399
425381264194 845688398
425381264697 845688399.

Выводы

Разобрали разные методы решения 25-х задачек на маски. Решили несколько задачек, среди которых были как самые простые, так и довольно интересные. Способ решения следует выбирать в зависимости от постановки.

Надеемся, материал был для вас полезен =)