Задача 25 ЕГЭ по информатике в 2024 г.

Хотите готовиться со мной к ЕГЭ?
Пишите: ydkras@mail.ru
Немного обо мне.

 

 В 2022 году задача 25 ЕГЭ по информатике сильно изменилась. В ней требуется проверять соответствие числа маске - символьной строке, в которой, кроме цифр, могут присутствовать символы '?' и '*'. Символ '?' означает любую произвольную цифру, а '*' - любую последовательность цифр, возможно, пустую (нулевой длины). Такая же задача приводится и в демо-варианте 2024 г. 

Данная задача решается очень просто. В питоне есть модуль fnmatch, содержащий функцию fnmatch. Данная функция как раз проверяет соответствие символьной строки маске, составленной по приведенным выше правилам. С помощью этой функции задачи такого типа решаются буквально в 3-4 строки.

Возьмем, к примеру, задачу 25 из демо-варианта 2024 г.:

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

— символ «?» означает ровно одну произвольную цифру;

— символ «*» означает любую последовательность цифр произвольной длины; в том числе «*» может задавать и пустую последовательность.

Например, маске 123*4?5 соответствуют числа 123405 и 12300405.

Среди натуральных чисел, не превышающих 10¹⁰, найдите все числа, соответствующие маске 1?2157*4, делящиеся на 2024 без остатка. В ответе запишите в первом столбце таблицы все найденные числа в порядке возрастания, а во втором столбце  — соответствующие им результаты деления этих чисел на 2024. 

Разумеется, проверять на сооветствие маске  и делимость на 2024 всех чисел, не превышающих 10 миллиардов - это нереально. Так как нас интересуют только числа, кратные 2024, то будем брать только эти числа и проверять их на соответствие маске. Тем самым мы сократим количество вариантов в 2000 с лишним раз, с 10 миллиардов до 5 миллионов. Тоже немало, но это уже в пределах возможностей компьютера, который дадут в ваше распоряжение на ЕГЭ.

Программа следующая:

import fnmatch
for n in range(2024,10**10+1,2024):
    if fnmatch.fnmatch(str(n),'1?2157*4'):
        print(n,n//2024)

Думаю, особых пояснений она не требует. Выполняется достаточно быстро, за несколько секунд.

Подобным же образом решаются все задачи 25 из ЕГЭ 2023 г., которые я видел.

Однако есть риск, что составители заданий для ЕГЭ поймут, что задача решается слишком просто, и немного изменят правила игры, так что замечательная функция fnmatch окажется бесполезной для наших целей. Может, этого и не случится, но, как известно, "надейся на лучшее - но готовься к худшему". Давайте попробуем представить варианты этого худшего и подумаем, как им можно противостоять.

Другой смысл у символов маски

Вполне возможно, что в задачах у символов маски станет немного другой смысл. Скажем, '?' будет обозначать не любую цифру, а только четную, а '*' - последовательность, которая состоит только из нечетных цифр.

Возможный выход - написать совокупность условий для проверки соответствия числа и маски.

Пусть наша маска - '1?2157*4', но '?' - одна четная цифра, а '*' - последовательность нечетных цифр.

Тогда условия для соответствия некоторой строки s данной маске могут быть, например, следующими:

len(s)>=7 and s[0]=='1' and s[1] in '02468' and s[2:6]=='2157' and s[-1]=='4' and oddonly(s[6:-1])

Функция oddonly(t) проверяет, что строка t состоит только из нечетных цифр (написание такой функции предоставляется читателю в качестве упражнения).

Громоздко? Да, есть такое дело. Поэтому я порекомендую другой выход из положения, а именно регулярные выражения.

Регулярные выражения

Регулярные выражения - очень мощный (с одной стороны) и сложный (с другой стороны) инструмент. Поэтому рассмотрим лишь очень немногие возможности регулярных выражений, которые можно использовать при решении данной задачи.

Для нас достаточно считать, что регулярные выражения - это некие шаблоны. Чтобы их использовать, следует импортировать модуль re. Функция re.fullmatch(s,p) проверяет строку s на соответствие шаблону p. 

Шаблоны - это строки, состоящие из обычных символов и символов, имеющих специальное значение. Из последних рассмотрим только символы '[', ']' и '*'.

Квадратные скобки используются для определения символов, которые могут встретиться в данном месте строки.  В квадратных скобках можно указывать символы и/или диапазоны символов (через знак "минус"). Например, шаблону 'к[ои]т' соответствуют строки 'кот' и 'кит', а шаблону '1[2-4]6' - строки '126', '136' и'146'.

Если после квадратных скобок стоит символ '*', то это означает строку произвольной (возможно, нулевой) длины, составленную из символов, перечисленных в скобках. Так, шаблон 'a[02468]b' обозначает строку, которая начинается с 'a', кончается на 'b', а между этими буквами находится произвольная последовательность четных цифр.   

Перепишем нашу предыдущую программу. Вместо функции fnmatch применим регулярные выражения:

import re
for n in range(2024,10**10+1,2024):
    if re.fullmatch('1[0-9]2157[0-9]*4',str(n)):
        print(n,n//2024)

В шаблоне фрагмент '[0-9]' обозначает одну произвольную цифру, а фрагмент '[0-9]*' - строку цифр любой длины.

Теперь если нам скажут, что знак вопроса обозначает не любую цифру, а только четную, а звездочка - это последовательность исключительно нечетных цифр, то это нас не напугает: мы слегка изменим наш шаблон на '1[02468]2157[13579]*4' - и все дела.

Более подробно с регулярными выражениями и их возможностями можно ознакомиться, например, тут: Регулярные выражения в Python от простого к сложному.

Впрочем, рассмотренных возможностей достаточно, чтобы не бояться условий типа  "символ '?' означает ровно одну нечётную цифру, кратную трём, а символ '*' означает любую последовательность чётных цифр произвольной длины". (Теперь-то мы знаем, что в шаблоне вместо знака вопроса надо будет написать '[39]', а вместо звездочки - '[02468]*'.)

"Вход с противоположной стороны"

 Все задачи № 25, предлагавшиеся в этом году (и в демо-варианте 2024 г.), требуют найти числа, которые 1) соответствуют некоторой маске и 2) делятся на некое число. Математики сказали бы, что требуется найти пересечение множества А (чисел, соответствующих маске) и множества В (чисел, кратных некоторому числу). 

Как мы решали эту задачу? Мы перебирали числа из множества В (кратные 2024) и проверяли, соответствуют ли они маске (принадлежат ли множеству А). Но можно поступить и наоборот: генерировать числа, соответствующие маске, и проверять, делятся ли они на требуемое число.

Когда оправдан такой подход? Очевидно, в тех случаях, когда наше "множество В" слишком велико (скажем, десятки или сотни миллионов чисел), так что его перебор займет слишком много времени. Если в "множестве А" элементов гораздо меньше, то такой подход - это, пожалуй, единственный способ справиться с задачей.

Рассмотрим этот подход на примере приведенной выше задачи. Нам надо сгенерировать все числа, соответствующие маске '1?2157*4' и не превышающие 10**10. 

Если число не превышает 10**10, то в нем самое большее 11 цифр - это как раз 10**10, т.е. 10000000000. Но данное число маске не соответствует, поэтому надо рассматривать лишь числа, состоящие не более чем из 10 цифр. Это означает, что строка, которая соответствует звездочке, может состоять максимум из трех цифр. Значит, надо получить все возможные строки из цифр длиной 0, 1, 2 и 3.

Вот один из способов сделать это:

 

star=['']
digits='0123456789'
for c1 in digits:
    star.append(c1)
for c1 in digits:
    for c2 in digits:
        star.append(c1+c2)
for c1 in digits:
    for c2 in digits:
        for c3 in digits:
            star.append(c1+c2+c3)

 

Заметим, что в массиве star 1111 элементов. Это означает, что в сочетании с произвольной цифрой на месте знака вопроса нам придется рассмотреть и проверить на делимость лишь 11110 чисел, что почти в 500 раз меньше, чем количество чисел, делящихся на 2024. Следовательно, данный способ решения задачи раз в 500 быстрее, чем прежний. 

Можно сгенерировать массив из строк чисел и с помощью более короткого кода, если воспользоваться модулем itertools. Код следующий:

import itertools
star=['']
digits='0123456789'
for m in range(1,4):
    for p in itertools.product(digits,repeat=m):
        star.append(''.join(p))

 

Операция join превращает кортеж символов p в строку.

А если воспользоваться генератором списков, то можно получить нужный список буквально в одну строку:

 

import itertools
digits='0123456789'
star=[''.join(p) for m in range(4) for p in itertools.product(digits,repeat=m)]

 

Вот полная программа для решения нашей задачи:

import itertools
star=['']
digits='0123456789'
for m in range(1,4):
    for p in itertools.product(digits,repeat=m):
        star.append(''.join(p))
a=[]
for d in digits:
    for s in star:
        n=int('1'+d+'2157'+s+'4')
        if n%2024==0:
            a.append(n)
a.sort()
for x in a:
    print(x,x//2024)

 

Разумеется, этот код гораздо длиннее, чем написанный нами ранее. Но генераторы списков позволяют его очень сильно сократить:

import itertools
digits='0123456789'
star=[''.join(p) for m in range(4) for p in itertools.product(digits,repeat=m)]
a=sorted([int(f'1{d}2157{s}4') for d in digits for s in star if int(f'1{d}2157{s}4')%2024==0])
for x in a:
    print(x,x//2024)

 

Ради краткости здесь также был использован аппарат форматированных строк: вместо выражения '1'+d+'2157'+s+'4' я писал f'1{d}2157{s}4'.

Новый код не намного больше, чем наше первое решение.

Так как в некоторых задачах количество чисел, которые делятся без остатка на некое число, очень велико, это делает невозможным решение по принципу "берем очередное кратное число - проверяем по маске" из-за неприемлемо большого времени вычислений. Возьмем, к примеру, задачу из ЕГЭ 2022 г.:

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

Если мы будем проверять числа, кратные 23, на соответствие маске, то нам придется сделать 10⁹/23 проверок, т.е. более 40 миллионов. Если же мы будем генерировать числа, соответствующие маске, то таких чисел всего-то навсего 100. Вот программа для решения данной задачи:

 

digits='0123456789'
for c1 in digits:
    for c2 in digits:
        n=int('12345'+c1+'7'+c2+'8')
        if n%23==0:
            print(n,n//23)

И этот код можно немного сократить, если использовать генераторы списков:

digits='0123456789'
a=[int('12345'+c1+'7'+c2+'8') for c1 in digits for c2 in digits]
for n in a:
    if n%23==0:
        print(n,n//23)

В заключение - совет не пренебрегать и "классическими" задачами на эту тему: поиск делителей, простые числа и пр. Так, простой факт, что если общее количество делителей некоторого числа нечетно, то это число является точным квадратом, может очень сильно уменьшить количество чисел, подлежащих перебору. Я уже написал статью на эту тему: Задача 25 ЕГЭ по информатике: разложение на множители, простые числа, количество делителей. За подробностями отсылаю к этой статье.

 

(c) Ю.Д.Красильников, 2024 г.