В этой статье рассмотрим некоторые прототипы заданий № 24 из ЕГЭ по информатике и изучим основные приёмы для обработки символьной информации.
Термины, которые мы будем использовать: строка, подстрока, обработка символьной последовательности. [i]
Основные методы строк
- S.find(str, [start],[end]) | Поиск подстроки в строке. Возвращает номер первого вхождения или −1.
- S.rfind(str, [start],[end]) | Поиск подстроки в строке. Возвращает номер последнего вхождения или −1.
- S.replace(шаблон, замена[, maxcount]) | Заменяет в строке S все вхождения подстроки old на подстроку new, count раз.
- S.split(символ) | Разбиение строки по разделителю.
- S.isdigit() | Состоит ли строка из цифр.
- S.isalpha() | Состоит ли строка из букв.
- S.isspace() | Состоит ли строка из неотображаемых символов (пробел, символ перевода страницы («\f»), «новая строка» («\n»), «перевод каретки» («\r»), «горизонтальная табуляция» («\t») и «вертикальная табуляция» («\v»)).
- S.upper() | Преобразование строки к верхнему регистру.
- S.lower() | Преобразование строки к нижнему регистру.
- S.join(список) | Метод строки join. У этого метода один параметр: список строк. В результате возвращается строка, полученная соединением элементов переданного списка в одну строку, при этом между элементами списка вставляется разделитель, равный той строке, к которой применяется метод.
- ord(символ) | Символ в его код ASCII.
- chr(число) | Код ASCII в символ.
- S.count(str, [start],[end]) | Возвращает количество непересекающихся вхождений подстроки в диапазоне [начало, конец] (0 и длина строки по умолчанию).
- S.lstrip([chars]) | Удаление пробельных символов в начале строки.
- S.rstrip([chars]) | Удаление пробельных символов в конце строки.
Чтение файла
С одной строкой:
f = open(«24.txt»)
s = f.readline()
f.close()
С множеством строк (разделённых знаком переноса на новую строку \n)
f = open(«24.txt»)
for s in f:
…
f.close() [i]
Функции MAX(), MIN()
Max(объект(или несколько), key = функция) [i]
| Код | Ответ | Пояснение |
| max([‘a’,’ab’,’acb’], key = len) | ‘acb’ | Находим, какой элемент списка больше по длине |
| max([1,2],[2,3,4], key = len) | [2, 3, 4] | Находим, какой список больше по длине |
| max([1,2],[2,3,4], key = max) | [2, 3, 4] | Находим, какой список больше по максимальному элементу каждого списка |
| max([2,2],[1,3,4], key = min) | [2, 2] | Находим, какой список больше по минимальному элементу |
Задание 1
В текстовом файле 24_1.txt находится цепочка из символов латинского алфавита A, B, C, D, E. Найдите длину самой длинной подцепочки, не содержащей символа D. [i]
f = open(’24_1.txt’)
s = f.readline()
mt, t = 0, 0
for i in range(len(s)): # Проходим по индексам строки
if s[i] != ‘D’: # Если перед нами не D
t += 1 # То увеличиваем длину подстроки и проверяем на максимум
mt = max(mt, t)
else:
t = 0 # Иначе сбрасываем счётчик
print(mt)
# Альтернативное решение
f = open(’24_1.txt’)
s = f.readline()
s = s.split(‘D’) # Делим получившиеся подстроки по знаку D
mt = 0
for x in s: # Проходим циклом по получившимся подстрокам
mt = max(mt, len(x)) # Проверяем на максимум
print(mt)
mt = len(max(s, key = len)) # Второй способ найти максимум
print(mt)
Ответ: 33.
Задание 2
Текстовый файл 24_2.txt состоит не более чем из 1 200 000 символов X, Y и Z. Определите максимальное количество идущих подряд символов, среди которых каждые два соседних различны. [i]
f = open(’24_2.txt’)
s = f.readline()
kt = 1 # Текущее количество; 1 знак точно берём для начала сравнения
kmax = 0
for i in range(len(s) — 1):
if s[i] != s[i+1]: # Если соседние знаки не одинаковы — это нам подходит,
# увеличиваем счётчик и проверяем максимум
kt += 1
kmax = max(kmax, kt)
else:
kt = 1 # Иначе начинаем с новым счётчиком искать следующую цепочку
print(kmax)
Ответ: 29.
Задание 3
Текстовый файл 24_3.txt состоит не более чем из 1 200 000 символов, которые являются прописными буквами латинского алфавита. Определите максимальное количество подряд идущих символов, среди которых нет символов A, B. [i]
f = open(’24_3.txt’)
s = f.readline()
maxk = 0
kt = 0
for i in range(len(s)):
if s[i] != ‘A’ and s[i] != ‘B’: # Если перед нами не A и не B, то подстрока нам подходит
kt += 1
maxk = max(maxk, kt)
else:
kt = 0 # Иначе обнуляем счётчик
print(maxk)
ИЛИ:
f = open(’24_3.txt’)
s = f.readline()
s = s.replace(‘B’,’A’) # Меняем знак, чтобы неподходящие буквы
выглядели одинаково
s = s.split(‘A’) # Делим по неподходящим знакам
print(len(max(s, key = len))) # Находим максимальную из длин
Ответ: 54.
Задание 4
Текстовый файл 24_1.txt состоит не более чем из 120 000 символов A, B, C, D и E. Определите максимальное количество идущих подряд символов, среди которых нет E, стоящих рядом. [i]
В этом задании мы не можем просто сплитить по E, потому что тогда мы теряем в длине подстроки. Например, в ABCEEABCEEDDDDE вместо EDDDDE мы получим DDDDE, что нам не подходит.
Поэтому сначала заменяем ‘EE’ на ‘E E’, чтобы после разделить по пробелам. Но после одной замены могут ещё остаться EE (при EEEE, мы получим E EE E, и у нас останется EE в центре), поэтому пишем while ‘ЕЕ’ in s:, чтобы изменить все имеющиеся две рядом стоящие буквы.
Программа:
f = open(’24.txt’)
s = f.readline()
while ‘EE’ in s: # Пока есть две рядом стоящие EE, заменяем их на ‘E E’
s = s.replace(‘EE’, ‘E E’)
s = s.split() # Делим по пробелам
print(len(max(s, key = len))) # Находим максимум по длине в полученных подстроках
# ИЛИ:
f = open(’24.txt’)
s = f.readline()
mt, t = 0, 1 # Текущий счётчик сразу равен 1, т. к. рассматриваем ПАРЫ чисел
for i in range(len(s) — 1):
if s[i] == ‘E’ and s[i+1] == ‘E’: # Если встретились две E подряд, сбрасываем счётчик до начального значения
t = 1
else:
t += 1 # Иначе увеличиваем его и проверяем на максимум
mt = max(mt, t)
print(mt)
Ответ: 8124.
Задание 5
Текстовый файл 24_1.txt состоит не более чем из 1 200 000 символов A, B, C, D и E. Определите максимальное количество идущих подряд символов, среди которых нет подстроки ACCB. Для выполнения этого задания следует написать программу. [i]
f = open(’24_1.txt’)
s = f.readline()
while ‘ACCB’ in s:
s = s.replace(‘ACCB’, ‘ACC CCB’) # Делаем замены, при которых могли бы
# забрать в подстроку максимальное число знаков
s = s.split()
print(len(max(s, key = len))) # Находим максимум по длине в полученных подстроках
ИЛИ:
f = open(’24_1.txt’)
s = f.readline()
maxk = 0
t = 3 # Изначальный счётчик = 3, как максимальное количество знаков, что мы 100%
# сможем взять в подстроку
for i in range(len(s) — 3): # Перебираем 4 соседних знака
if s[i] == ‘A’ and s[i+1] == ‘C’ and s[i+2] == ‘C’ and s[i+3] == ‘B’:
t = 3 # Сбрасываем счётчик, если нашлось ACCB
else:
t += 1
maxk = max(t, maxk) # Иначе увеличиваем его и проверяем на максимум
print(maxk)
Ответ: 2139.
Задание 6
Текстовый файл (досрочная волна 2025) состоит из десятичных цифр и заглавных букв латинского алфавита. Определите в этом файле последовательность идущих подряд символов, представляющих собой запись максимального чётного 14-ричного числа. В ответе запишите количество символов (значащих цифр в записи числа) в этой последовательности.
Примечание. Латинские буквы A, B, C и D означают цифры из алфавита 14-ричной системы счисления. [i]
Решим задание двумя циклами.
Чтобы быстрее произвести замену, импортируем алфавит в какую-то переменную от четвёртого знака алфавита и до конца (это те числа, что НЕ могут быть в нужной нам сс). Теперь заменяем циклом все эти знаки на * и проверяем, что в нужной нам подстроке их нет. Число должно быть чётным, поэтому его последний символ обязан быть одной из чётных цифр алфавита.
Программа:
import string
s = open(’24_25dosr.txt’).readline()
ma = 0
nealf = string.ascii_uppercase[4:] # Ненужные буквы алфавита
for x in nealf:
s = s.replace(x, ‘*’)
mt = » # Текущая наибольшая подстрока
ma = 0 # Длина наибольшей подстроки
for l in range(0, len(s)):
if s[l] != ‘0’: # Число не может начинаться с нуля
for r in range(l+ma, len(s)):
t = s[l:r+1]
if ‘*’ not in t:
if t[-1] in ‘02468AC’: # Если число чётное
if t > mt:
mt = t
ma = len(t)
else:
break
print(ma)
Ответ: 2598.
Задание 7
Текстовый файл (ЕГЭ 2025) состоит из десятичных цифр и заглавных букв латинского алфавита. Определите в прилагаемом файле последовательность из максимального количества идущих подряд символов, среди которых ровно 35 букв S, начинающуюся чётной цифрой, не содержащую других чётных цифр, кроме первой. В ответе запишите число — количество символов в найденной последовательности. Для выполнения этого задания следует написать программу. [i]
Решим методом двух указателей. Для удобства заменим все чётные цифры на один символ, например ‘2’.
Теперь запускаем два цикла: внешний — по левой границе подстроки, внутренний — по правой. Важно, чтобы первый символ был чётным. Срезом берём фрагмент в выбранном диапазоне и сначала проверяем условие, которое нам не подходит (больше одной чётной цифры или больше 35 букв S), — это позволяет быстрее отбрасывать неподходящие варианты. Если фрагмент всё ещё подходит, проверяем, что букв S ровно 35, и только тогда обновляем максимум.
Программа:
import string
s = open(’24_25osn.txt’).readline()
m = 0
s = s.replace(‘0′,’2’).replace(‘4′,’2’).replace(‘6′,’2’).replace(‘8′,’2’)
# Заменяем все чётные цифры на один знак
for l in range(len(s)):
if s[l] == ‘2’: # Первый знак чётный!
for r in range(l + m, len(s)):
t = s[l : r + 1]
if t.count(‘2’) > 1 or t.count(‘S’) > 35:
# Если нашли что-то неподходящее, то не рассматриваем эту цепочку дальше и # переходим к следующей
break
else:
if t.count(‘S’) == 35:
m = max(m, len(t))
print(m)
Ответ: 292.
Заключение
Задание № 24 почти всегда сводится к поиску самой длинной подпоследовательности, удовлетворяющей некоторому условию. Два надёжных приёма: пройти строку одним циклом, наращивая счётчик и сбрасывая его на «запрещённом» символе, либо заменить разделители так, чтобы строку можно было разбить методом split() и взять самый длинный кусок. Для более сложных условий (как в заданиях 6 и 7) применяют метод двух указателей с предварительной заменой символов.
