Задачи со сложными шаблонами в №24

Задачи со сложными шаблонами в №24

👋 Блин, мне так полюбился такой серийный формат, вы не представляете. Уже есть 5 кайфовых постов по разным типам и способам решения 24 задач, а как закончу - соберу всё в виде экспертной статьи в разделе "Учебник" на bank-kege.ru. Сегодня продолжаем! Поговорим про тип, массово появившийся на ЕГЭ-2024, от которого все просто обалдели. Именно после этих задач стало модно давать ученикам решение через регулярки, чтобы хоть как-то выходить из положения)

✅ Повторяющиеся комбинации

✅ Запрещённые комбинации

✅ Ограниченное количество

👉 Сложные шаблоны (сейчас)

🔜 Несколько строк

🔜 Частотный анализ

Как всегда без душной теории и малейшей капельки вазелина сразу переходим к практике! Возьмем задачу №24.10021 с bank-kege.ru

Условие:

Текстовый файл состоит из символов, обозначающих знаки « – », « * » и цифры 0, 7, 8, 9. Определите в прилагаемом файле максимальное количество идущих подряд символов, которые образуют математически правильную последовательность, в которую входят знаки « – » или « * » и натуральные числа без незначащих нулей.

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

Идея: Пишем регулярку, находим все подходящие под нее подстроки, выбираем самую длинную. Типа всё. Как написать регулярку? Начнем с натурального числа. Оно начинается с ненулевой цифры, за которой следует любое количество (от 0) любых цифр. А в регулярку арифметического выражения будем подставлять числа с помощью f-строк: число, знак, число, знак итд.

Код:

from re import *

s = open('24.10021.txt').readline()

num = r'([1-9][0-9]*)'

reg = rf'{num}([-*]{num})+'

print(max(len(i.group()) for i in finditer(reg, s)))

2⃣ Боль через replace() и split()

Идея: Заменяем все знаки на что-то одно, например, "-" на "*". Рубим строку по ним методом split(). Получаем список строк, которые должны быть натуральными числами для подходящих выражений. Будем циклом for их перебирать и проверять, что строка является натуральным числом, то есть непустая и не начинается с 0, тогда увеличиваем счетчик длины, не забывая про уничтоженный знак, и обновляем максимум. А если встретили не натуральное число, то тут, как говорится, всё фигня, давай по новой)

Код:

s = open('24.10021.txt').readline()

s = s.replace('-', '*')

a = s.split('*')

mx, cur_len = 0, 0

for part in a:

if part != '' and part[0] != '0':

cur_len += len(part) + 1

mx = max(mx, cur_len - 1)

# последний подсчитанный знак не берем

else:

cur_len = 0

print(mx)

И мы получим правильный ответ! НО!

Этот способ не учитывает, что если подстрока в списке начинается с нуля, то ее конец может быть началом нового подходящего выражения. Чтобы это исправить, надо отдельно рассматривать этот случай и брать конец строки с индекса первой ненулевой цифры.

Исправленный код:

s = open('24.10021.txt').readline()

s = s.replace('-', '*')

a = s.split('*')

mx, cur_len = 0, 0

for part in a:

if part != '' and part[0] != '0':

cur_len += len(part) + 1

mx = max(mx, cur_len - 1)

elif part == '':

cur_len = 0

else:

for i in range(len(part)):

if part[i] != '0':

cur_len = len(part[i:]) + 1

break

else:

cur_len = 0

print(mx)

Глядя на решение через регулярки кажется, что ларчик просто открывается, но только представьте, что большинство сдающих ЕГЭ-2024 их не знали, раньше не было в них не было в них необходимости, вот и приходилось извращаться как показано во втором способе((

Эта история учит, что если двигаться на понимании, то с помощью приземленных методов и функций вполне можно решить что-то новое. Приколы питона для всех случаев жизни выучить невозможно, а понять базовые идеи и наблатыкаться их применять даже в сложных ситуациях - вполне)

В домашку вам задача №24.10024. А для профессоров питона и ЕГЭ по информатике - №24.10022 - жесточайший гроб с реального ЕГЭ)

Голосование проводить не будем, просто накидывайте побольше 🔥, чтобы посты про оставшиеся типы вышли как можно быстрее, там будет самая жесткая экзотика))

#информатика

#задание24