Задачи №24 вызывают затруднения у многих, но на самом деле, если к ним подготовиться, можно понять, что это легкий балл на экзамене. Все использованные задачи с сайта К.Ю. Полякова
Вот задача Багдасаряна, № 8115. Формулировку привожу ниже:
№ 8115
Или вот так можно:
Подробнее об этой задаче тут (расписал каждую строчку подробно)
Давайте по порядку. Начнем с метода двойного цикла, от простого к сложному.
1. Метод перебора с помощью двойного цикла
начнем с простых задач. Все с сайта К.Ю. Полякова
№ 2518
(№ 2518) (А.М. Кабанов) В текстовом файле находится цепочка из символов латинского алфавита A, B, C, D, E, F. Найдите длину самой длинной подцепочки, не содержащей символа D.
Общий принцип - без оптимизации сложно, поэтому бежим по строке, выделяя цепочки символов, каждый раз эффективно вычисляя левую и правую границу, причем к левой границе прибавляем выбранный максимум - меньше максимума нам нет смысла обрабатывать "отрезки": цепочку символов строим с помощью среза. Также предлагаю вычислять время исполнения задачи с помощью модуля time
Но смотрите - длина строки всего 10240 символов - такую легкую задачу можно решить простым перебором символов за меньшее время. Но, как понимаете, это учебный пример - в ЕГЭ таких задач нет
Вот еще способ - с помощью замены 'D' на пробелы и потом с помощью метода split посчитать длины цепочек символов от пробела до пробела
Как видим, на малом наборе время почти не отличается. И, забегая вперед, вот решение задач с регулярными выражениями. Скорость, как понимаем, быстрее всех. И на больших наборах работает тоже быстро. Но об этом во второй части статьи
№ 4218
(№ 4218) Текстовый файл состоит не более чем из 106 символов и содержит только заглавные буквы латинского алфавита (A..Z). Определите максимальное количество идущих подряд символов, среди которых нет сочетания стоящих рядом букв P и R (в любом порядке).
Решение было найдено примерно за 1.147 секунды. Все нехитро - разобрались?
№ 6782
(№ 6782) (ЕГЭ-2023) Текстовый файл состоит не более чем из 106 символов и содержит только заглавные буквы латинского алфавита и цифры. Определите максимальную длину подстроки, в которой ни одна буква не стоит рядом с буквой и ни одна цифра не стоит рядом с цифрой.
- тут идея схожая с предыдущей задачей, но использовали замену, чтобы искать две буквы или две цифры
№ 6783
(№ 6783) (А. Рогов) Текстовый файл состоит не более чем из 106 символов и содержит только заглавные буквы латинского алфавита. Определите максимальное количество идущих подряд символов, среди которых любые два подряд идущих символа различны.
Здесь будем просматривать пары символов в цепочке (как в 17-й задаче ЕГЭ) и проверять их, что они не равны. ну и если это так, выбираем максимальную цепочку. Считает не так быстро, но за разумное время
№ 4184
(№ 4184) (Е. Джобс) Текстовый файл состоит не более чем из 106 символов и содержит только заглавные буквы латинского алфавита (ABC…Z). Найдите максимальную длину подстроки, в которой ни одна тройка символов не записана два раза подряд. Например, в искомой подстроке не может быть фрагмента ABCABC.
Задача не так проста - даже с оптимизацией выполняется долго. Кстати, вот вам лайфхак - чтобы понять, что вообще что-то считается и мы идем к ответу, можно внутри цикла прописать такую строчку и смотреть скорость работы
if l % 100000 == 0: print('выполняем...',l)
Здесь мы просматриваем 6 соседних символов, две тройки. Не забудьте поработать с длиной цепочки - чтобы у всех были соседи, идем до len(c)-5
Вот так выполняется код - почти 2 минуты. Это время называют разумным) Простым перебором никогда б не дождались
№ 4923
(№ 4923) Текстовый файл содержит строку из заглавных латинских букв X, Y и Z, всего не более чем из 106 символов. Определите максимальное количество идущих подряд пар символов ZX или ZY.
так как речь о парах, смотрим только те цепочки символов, длины которых четны, идем по символам с шагом 2, чтобы не смотреть пересечения. Не забываем потом разделить на 2 результат, ведь нас просят найти пары, а не количество символов в цепочке. Обратите внимание, что ветка else с прерыванием работы цикла закрывает цикл просмотра пар, а не проверку на четность длины цепочки. Времени потребовалось 3,5 секунды!
№ 5155
(№ 5155) (Е. Джобс) Текстовый файл содержит строку из заглавных латинских букв A, B и C, всего не более чем из 106 символов. Найдите максимальное количество подряд идущих пар символов AA или CC. Искомая подстрока может включать только пары АA, только пары CС или содержать одновременно как пары АA, так и пары CC.
Задача хитрая, регулярками решается непросто. А вот нашим методом - без проблем. Код похож на предыдущую задачу. Разница в 4 символах)
№ 5387
(№ 5387) (А. Калинин) Текстовый файл содержит строку из символов A, B, C и цифр 1, 2, 3, всего не более чем 106 символов. Определите максимальное количество идущих подряд пар символов вида «буква + цифра».
Замена просится в этой задаче - меняем буквы на А, цифры на 1, далее все по привычной схеме. Ответ 183
№ 5391
(№ 5391) Текстовый файл содержит строку из символов A, B, C и цифр 1, 2, 3, всего не более чем 106 символов. Определите максимальное количество идущих подряд троек символов вида «цифра + буква + цифра».
Здесь уже тройка символов, так что меняем двойки на тройки в нашем коде и дописываем третий элемент в цепочке. Ответ 164
№ 5228
(№ 5228) Текстовый файл содержит только заглавные буквы латинского алфавита (ABC…Z). Определите максимальное количество идущих подряд символов, среди которых буква A встречается не более пяти раз.
Задача на определение количества - используем метод .count
№ 7194
(№ 7194) Текстовый файл состоит не более чем из 106 символов и содержит только заглавные буквы латинского алфавита. Определите максимальное количество идущих подряд символов, среди которых буквы X, Y и Z встречаются ровно по пять раз.
Здесь нужно внимательно посмотреть на ветку else - обязательно прописываем elif, указывая, что x, y, z больше пяти, связка - or
№ 7202
(№ 7202) Текстовый файл состоит не более чем из 10^6 символов и содержит только заглавные буквы латинского алфавита. Определите максимальное количество идущих подряд символов, среди которых каждая из гласных букв (A, E, I, O, U, Y) встречается не более восьми раз, а буквы V, X и Z не встречаются совсем.
файл тот же, идея проще, хотя если не закрыть два раза выполнение цикла, он так и не посчитает вам ответ - см. внимательно else: break
№ 6147
(№ 6147) *(В. Петров) Текстовый файл состоит не более чем из 106 символов и содержит только заглавные буквы латинского алфавита и точки. Определите минимальное количество идущих подряд символов, среди которых ровно семь точек.
Задача со звездочкой, а решается нашим методом влет. Единственное отличие - ищем минимум - просто меняем max на min. Однако поработать необходимо с длиной цепочки - ставим for r in range(l, l+m): для правой границы, ну и break пишем сразу после того как нашли минимум
№ 3529
(№ 3529) (А. Кабанов) Текстовый файл содержит строку из заглавных букв A, B, C, D, E, F, всего не более чем из 10^6 символов. AF-подстроками назовём последовательности символов A, B, C, D, E, F, ограниченные в начале символом A, а в конце символом F (граничные символы входят в подстроку). Определите минимальную длину AF-подстроки. Подстроки, состоящие из двух символов, не учитывать.
И снова минимум ищем плюс хитрости - см.код. Хитрости в определении правой границы for r in range(l+2, l+m), а так, все просто и логично
№ 6674
(№ 6674) (ЕГЭ-2023) Текстовый файл состоит не более чем из 10^6 символов и содержит только заглавные буквы латинского алфавита. Определите минимальную длину подстроки, в которой символ Z встречается не менее 120 раз.
Задача непростая. И да, если думаете, что минимум не попросят найти на ЕГЭ, ошибаетесь - вот задача с реального экзамена 2023 года. Снова играем с правой границей, идем в обратную сторону for r in range(l+m, l, -1):. Считает быстро, но все равно строчку проверки скорости вставлю
№ 6676
(№ 6676) (ЕГЭ-2023) Текстовый файл состоит не более чем из 106 символов и содержит только заглавные буквы латинского алфавита и цифры. Определите максимальную длину подстроки, которая может являться записью числа в шестнадцатеричной системе счисления.
Про системы счисления задач стало больше, готовьтесь. Сложности нет, но надо быть аккуратным. Идея проста - меняем все буквы, которые не могут участвоват ь в записи 16-ного числа на пробел и проверяем длины цепочек, которые не должны начинаться с нуля и не содержать пробел. Секунда - и ответ на экране
№ 8074
(№ 8074) (Досрочный ЕГЭ-2025) Текстовый файл состоит не более чем из 106 символов и содержит только десятичные цифры и заглавные буквы латинского алфавита. Определите в этом файле максимальное количество идущих подряд символов, которые могут представлять запись чётного числа в двенадцатеричной системе счисления. В этой записи отсутствуют незначащие (ведущие) нули. Цифры, числовое значение которых превышает 9, обозначены латинскими буквами, начиная с буквы А.
Все тоже несложно - надо лишь понять, что такое четное число в 12-чной системе счисления. А это числа, последние цифры в которых из набора '02468A', ну и добавить в набор "плохих" цифр еще CDEF надо.
Итак, надеюсь, все было понятно. С вас 👍, если было полезно. Переходим к изучению регулярных выражений
Регулярные выражения. Решение задач
Решим задачу выше с досрока 2025 (№ 8074) этим способом. Оказывается скорость гораздо выше у регулярок. Огромный файл был обработан за доли секунды
Итак, по порядку.
Регулярные выражения в Python — это шаблоны для поиска нужных фрагментов текста. 1 Они позволяют искать, извлекать, заменять и разделять строки на основе заданных шаблонов. Для работы с регулярными выражениями в Python используется встроенный модуль re
В предлагаемом способе мы будем использовать функцию finditer(шаблон, строка), которая быстро ищет вхождения подстрок, подходящие под регулярное выражение)
Мы будем записывать выражения в неэкранированные строки (r' - сырая строка, или raw string), где все символы используются не как специальные.
Про квантификаторы.
Квантификаторы в регулярных выражениях – это специальные символы, которые указывают, сколько раз определённый элемент (символ, группа или класс символов) должен повторяться в рассматриваемой строке. Примеры - ниже
- A* - пустота или много букв А
- A+ - одна буква А обязательно или много букв А
- А {5} - ровно пять букв А
- А {2,5} - от 2 до 5 букв А (АА, ААА, АААА, ААААА)
Символьные классы
- [ABC] {4} - сочетания из набора в 4 символа (BCAA, ACBB и т.д)
- [0-9] {3} - любой символ из диапазона (используется код символа) (132, 234)
- [^CDE] - не С,D и не Е
- .А (. - любой произвольный символ) BA, 7A, #A и так далее
- если символы проверяются как обычные, то перед ними надо поставить \ (например, \. или \+)
Скобочные группы
- () - запоминающие скобки
- (?=()) - поиск всех возможных совпадений, включая пересечения
- AB | CD | XY - AB или CD или XY
- примеры: [AB]+ если в квадратных скобках AB, то ищем подряд идущие символы A или B, а если в круглых (AB)+ то пары AB идут подряд
Понятнее будет на примерах.
№ 2510
(№ 2510) (А.М. Кабанов) В текстовом файле находится цепочка из символов латинского алфавита A, B, C, D, E. Найдите длину самой длинной подцепочки, состоящей из символов A, B или C (в произвольном порядке).
задача учебная, легкая, набор маленький. Коротко об идее:
Создаем регулярку в переменную reg, пробегаемся по всей строке s и функцией finditer просматриваем все цепочки символов, подходящих под шаблон reg, собирая их в группы методом .group() - ну и по пути вычисляем их длины, а на экран выводим максимальную длину. Просто? Еще и быстро!
№ 4923
(№ 4923) Текстовый файл содержит строку из заглавных латинских букв X, Y и Z, всего не более чем из 106 символов. Определите максимальное количество идущих подряд пар символов ZX или ZY.
Видим или - ставим прямой слэш. Раз пары конкретные, заключаем в круглые скобки, не забываем плюсик в конце. Ну и так как нас спрашивают пары, а не количество символов, делим максимум на 2. Обратите внимание на скорость - доли секунды обрабатывает 1000000 символов, а ведь finditer смотрит ВСЕ символы строки
№ 5327
(№ 5327) (ЕГЭ-2022) Текстовый файл содержит строку из набора A, B, C, D, O, всего не более чем из 106 символов. Определите максимальное количество идущих подряд пар символов вида «согласная + гласная».
Видится, что здесь можно заменить символы, но можно и без замены. Известно, что сначала идут согласные, потом гласные, поэтому группу символов так и прописываем r'([BCD][AO])+'
Всего 10068 символов, может быть, с replace попробуем? Работает чуть дольше, ответ тот же
№5155
Эту задачу мы уже решали выше методом двойного цикла, но сейчас интересно на нее взглянуть с другой стороны. Ведь тут возможны пересечения пар, поэтому надо продумать логику решения. Ответ правильный, время - на 11 секунд быстрее, чем методом вложенного цикла.
Идея решения проста, но есть нюансы. Объясню: регулярка ясная - пары АА или СС, но нужно проверить и их пересечения - с помощью 'f строки подставим в скобочную группу для проверки пересечений ?=({reg}). Важный нюанс - надо в методе group(1) указать единицу - мы берем максимальную группу, она первая из двух. Без этих действий ответ будет 1305 (без учета пересечений)
№ 5391
такую задачу мы уже решали выше, но давайте вторым способом с ней разберемся. Способ работает в несколько раз быстрее. Кстати, проверку на пересечения можно вставлять в любой задаче и проверить себя rf'(?=({reg})). Здесь ответ будет такой же. Но при этом единицу в груп вставить не забудьте. так как проверяем тройки, делим на 3 количество символов - будьте внимательны!
№ 5936
(№ 5936) (Е. Джобс) Текстовый файл состоит не более чем из 106 символов и содержит только заглавные буквы латинского алфавита X, Y и Z. Найдите максимальную длину подстроки, которая состоит из сочетаний XY, YZ, YZZ, записанных в произвольном порядке. В ответе укажите наибольшую длину подходящей подстроки. Например, в строке ZZXZXZZXYYZYZZYYY самая длинная подходящая подстрока – XYYZYZZ имеет длину 7.
Автор - Е.Джобс, а это значит, что вероятность хитрости в задаче повышенная, надо перечитать. А хитрость в том, что первой надо перебирать сочетание YZZ, потом уже XY и YZ - ответы будут разные, ну и обязательно перебирать пересечения (хотя тут получился тот же ответ). Ответ сошелся, секунду выполнялась программа.
980000 314 0.07520818710327148 - это результаты вывода без проверки сочетаний
Выше - результат решения при неправильном подходе просмотра групп символов, ответ другой
№ 7497
(№ 7497) (ЕГЭ-2024) Текстовый файл состоит не более чем из 10^6 символов и содержит только символы, обозначающие знаки «-», «*», и цифры 0, 7, 8, 9. Определите в прилагаемом файле максимальное количество идущих подряд символов, которые образуют математически правильную последовательность, в которую входят знаки «-» или «*» и натуральные числа без незначащих нулей.
А вот и типичная задача, которую надо решать регулярками. оформим натуральное число отдельно в регулярку, далее с помощью f-строки подставим в паттерн. На примере этой задачи посмотрим, как выводить не только максимальную длину цепочки, но и саму цепочку для визуального просмотра.
Идея простая - в регулярку записываем число таким образом: r'([1-9][0-9]*)', ведь число не может начаться с нуля, но в целом его может ин е быть - ставим звездочку. В основной регулярке будьте внимательны со скобками - reg = rf'{n}([*-]{n})+'
- Или вот - решение с ключом по длине. Визуально смотрим цепочку, глазами проверяем ее
№ 7966
(№ 7966) Текстовый файл состоит не более чем из 10^6 символов и содержит только цифры шестнадцатеричной системы счисления, а также знаки «+» и «*» (сложения и умножения). Определите максимальное количество символов в непрерывной последовательности, которая является корректным арифметическим выражением с целыми неотрицательными числами, записанными в троичной системе счисления. В этом выражении никакие два знака арифметических операций не стоят рядом, в записи чисел отсутствуют незначащие (ведущие) нули и число 0 не имеет знака.
Интересная задача, про системы счисления опять же. Есть одна хитрость - число может быть нулем, то есть регулярка будет выглядеть вот так: r'([12][012]*|0)' - будьте внимательны!
№ 7573
(№ 7573) (ЕГЭ-2024) Текстовый файл состоит не более чем из 10^6 символов и содержит только десятичные цифры, а также знаки «+» и «*» (сложения и умножения). Определите максимальное количество символов в непрерывной последовательности, являющейся корректным арифметическим выражением с целыми неотрицательными числами (без знака), значение которого равно нулю. В этом выражении никакие два знака арифметических операций не стоят рядом, порядок действий определяется по правилам математики. В записи чисел отсутствуют незначащие (ведущие) нули. В ответе укажите количество символов в найденном выражении.
Этой задаче я бы поставил звездочку. И, надо отметить, в 2024 году эта задача была у кого-то на экзамене. Решаем регулярными выражениями, но небыстро. Много сложностей и костылей, но решить удалось.
№ 7786
(№ 7786) Текстовый файл состоит не более чем из 10^6 символов и содержит только цифры шестнадцатеричной системы счисления, а также знаки «+» и «*» (сложения и умножения). Определите максимальное количество символов в непрерывной последовательности, которая начинается символами AF, за которыми следует правильное арифметическое выражение с целыми неотрицательными числами (без знака), записанными в десятичной системе счисления. В этом выражении никакие два знака арифметических операций не стоят рядом. В записи чисел отсутствуют незначащие (ведущие) нули. В ответе укажите количество символов в найденном выражении.
Эта задача, по сравнению с прошлой, легкая, давайте закончим на позитивной ноте. Здесь мы пишем регулярку как читаем, без изыска и сложностей
Любопытная задача А. Рогова с пробника №12 - для интереса читайте тут как ее решил разными способами. А сейчас разберем демоверсию 2025 года. задача тоже интересная, с маленьким нюансом
Демо 2025
Здесь нюанс с нулем - мы, оказывается, можем умножать на ноль, вычитать из нуля и т.д, поэтому регулярка будет выглядеть вот так:
Итак, вот и подошла к концу статья с разборами задач. надеюсь, было полезно - в этом случае ставьте пальчик вверх 👍 Пишите вопросы и предложения