Решение 24ой задачи методом двойного цикла раньше никогда не разбиралось, несмотря на то, что этот метод чрезвычайно прост и эффективен, он позволяет решать практически все задания, которые относятся к 24ой задаче ЕГЭ.
Посмотрим, как будет работать двойной цикл, перебирающий разные подстроки внутри строки – для примера возьмем короткую строку s = ‘ABCD’ и выведем на экран разные подстроки с, которые перебирает двойной цикл, в котором внешний перебирает левую границу подстроки, а внутренний – правую:
Подстроки с выглядят следующим образом:
Надо отметить, что именно таким образом писать цикл для перебора строки s из файла нельзя, потому что в строке может быть огромное количество символов, и цикл, написанный таким способом, будет работать чрезвычайно долго. Для того, чтобы циклы выполнялись достаточно быстро, циклы нужно оптимизировать, добавить в них ограничения.
Задача № 1
В текстовом файле k7a-3.txt находится цепочка из символов латинского алфавита A, B, C, D, E, F. Найдите длину самой длинной подцепочки, состоящей из символов A, B, E, F (в произвольном порядке).
Решение
Сохраним файл k7a-3.txt и считаем его, преобразовав в строку с помощью команды s = open(‘files/k7a-3.txt’).readline().
Заведем переменную m, изначально равную нулю, она будет использоваться для хранения максимальной длины подстроки, состоящей из символов A, B, E, F. Напишем двойной цикл, который будет перебирать все возможные подстроки внутри строки s. Внешний цикл будет перебирать все возможные левые границы подстроки, начиная с первого символа и до последнего. Внутренний цикл будет проверять все возможные правые границы подстроки. Правый индекс начинается с l + m, где m — это текущий максимум длины подстрок, состоящей из символов A, B, E, F. Это оптимизация, которая позволяет не искать подстроки длиной меньше уже найденных. Извлекаем подстроку c, начиная с индекса l и заканчивая индексом r включительно. Проверяем, что подстрока состоит из символов A, B, E, F, то есть не содержит символов ‘C’ и ‘D’. Если это условие выполняется, то текущая подстрока считается допустимой, в этом случае обновляется максимальная длина, счетчик m. Если в подстроке найден запрещенный символ (‘C’ или ‘D’), то цикл прерывается, так как дальше искать подстроки с более длинными правыми границами нет смысла — они уже будут включать запрещенные символы.
В завершение программы выводим на экран найденное значение m, это ответ на задачу.
s = open(‘files/k7a-3.txt’).readline()
m = 0
for l in range(len(s)):
for r in range(l+m,len(s)):
c = s[l:r+1]
if ‘C’ not in c and ‘D’ not in c:
m = max(m, len(c))
else:
break
print(m)
Ответ: 20
Задача №2
Текстовый файл 24-157.txt состоит не более чем из 106 символов и содержит только заглавные буквы латинского алфавита (A..Z). Определите максимальное количество идущих подряд символов, среди которых нет сочетания символов QW.
Решение
Сохраним файл 24-157.txt и считаем его, преобразовав в строку с помощью команды s = open(‘files/24-157.txt’).readline().
Заведем переменную m, изначально равную нулю, она будет использоваться для хранения максимальной длины подстроки, которая не содержит сочетания символов QW. Создадим цикл, который будет перебирать все возможные левые границы подстроки, начиная с первого символа и до последнего. Внутренний цикл будет проверять все возможные правые границы подстроки. Правый индекс начинается с l + m, где m — это текущий максимум длины подстроки без сочетания символов QW. Это оптимизация, которая позволяет не искать подстроки длиной меньше уже найденных. Извлекаем подстроку c, начиная с индекса l и заканчивая индексом r включительно. Проверяем, что подстрока c не содержит сочетания символов QW. Если это условие выполняется, то текущая подстрока считается допустимой, в этом случае обновляется максимальная длина, счетчик m, ему соответствует максимальное значение между текущим значением m и длиной текущей подстроки . Если подстрока содержит сочетание символов QW, выполнение внутреннего цикла прерывается с помощью команды break. Это означает, что подстроки с правой границей, начиная с текущего индекса r, уже не будут проверяться для текущего значения левой границы l.
В завершение программы выводим на экран найденное значение m, это ответ на задачу.
s = open(‘files/24-157.txt’).readline()
m = 0
for l in range(len(s)):
for r in range(l+m,len(s)):
c = s[l:r+1]
if ‘QW’ not in c:
m = max(m,len(c))
else:
break
print(m)
Ответ: 5267
Задача № 3
Текстовый файл 24-263.txt состоит не более чем из 106 символов и содержит только заглавные буквы латинского алфавита. Определите максимальную длину подстроки, в которой символ Y встречается не более 150 раз.
Решение
Сохраним файл 24-263.txt и считаем его, преобразовав в строку с помощью команды s = open(‘files.24-263.txt’).readline(). Заведем переменную m, изначально равную нулю, она будет использоваться для хранения максимальной длины подстроки внутри которой символ Y встречается не более 150 раз. Создадим цикл, который будет перебирать все возможные левые границы подстроки, начиная с первого символа и до последнего. Внутренний цикл будет проверять все возможные правые границы подстроки. Правый индекс начинается с l + m, где m — это текущий максимум длины подстроки, внутри которой символ Y встречается не более 150 раз. Внутри вложенного цикла извлекаем подстроку c из строки s, которая начинается с индекса l и заканчивается индексом r включительно. Проверяем, что в подстроке c символ Y встречается не более 150 раз с помощью метода c.count. Если это условие выполнено, то программа продолжает работу и обновляет максимальную длину, счетчик m. После того как оба цикла завершены, выводится максимальная длина подстроки, внутри которой символ Y встречается не более 150 раз.
s = open(‘files/24-263.txt’).readline()
m = 0
for l in range(len(s)):
for r in range(l+m,len(s)):
c = s[l:r+1]
if c.count(‘Y’)<=150:
m = max(m,len(c))
else:
break
print(m)
Ответ: 5195
Задача № 4
Текстовый файл состоит из символов A, B, C, D, E и F.
Определите максимальное количество идущих подряд символов в прилагаемом файле, среди которых пара символов CD (в указанном порядке) встречается ровно 160 раз.
Для выполнения этого задания следует написать программу.
Файлы к заданию: 24.txt
Решение
Сохраним файл 24_17535.txt и считаем его, преобразовав в строку с помощью команды s = open(‘files.24_17535.txt’).readline(). Заведем переменную m, изначально равную нулю, она будет использоваться для хранения максимальной длины подстроки, внутри которой пара символов CD встречается ровно 160 раз. Создадим цикл, который будет перебирать все возможные левые границы подстроки, начиная с первого символа и до последнего. Внутренний цикл будет проверять все возможные правые границы подстроки. Правый индекс начинается с l + m, где m — это текущий максимум длины подстроки, внутри которой пара символов CD встречается ровно 160 раз. Внутри вложенного цикла извлекаем подстроку c из строки s, которая начинается с индекса l и заканчивается индексом r включительно. Создаем переменную k, которая равна количеству пар символов CD (используем метода c.count). Проверяем, если k = 160, то программа продолжает работу и обновляет максимальную длину, переменную m. Если k превышает 160, то программа прерывается.
После того как оба цикла завершены, должны выводиться максимальная длина подстроки, внутри которой пара символов CD встречается ровно 160 раз, но в строке огромное количество символов, поэтому ждать ответа приходится долго.
Поэтому будем выводить промежуточные результаты каждый раз, когда значение l делится на 100 000 без остатка. В выводе показываются: m: текущий максимальный размер подходящей подстроки, l: текущий индекс начала подстроки, len(s): длина всей строки.
Это нужно для того, чтобы отслеживать прогресс работы программы на больших входных данных.
s = open(‘files/24_17535.txt’).readline()
m = 0
for l in range(len(s)):
for r in range(l+m,len(s)):
c = s[l:r+1]
k = c.count(‘CD’)
if k==160: m = max(m,len(c))
elif k>160: break
#вывод промежуточного результата каждые 100 000 итераций
if l%100_000==0: print(m,l,len(s))
Ответ: 9712
Задача №5
Текстовый файл 24-263.txt состоит не более чем из 106 символов и содержит только заглавные буквы латинского алфавита. Определите минимальную длину подстроки, в которой символ Z встречается не менее 120 раз.
Решение
Задача отличается от предыдущих тем, что нам нужно найти не максимальную, а минимальную длину строки, будем писать такой цикл, который начинает работу с рассмотрения максимально длинной подстроки, а затем сокращает её до минимально возможной.
Сохраним файл 24-263.txt и считаем его, преобразовав в строку с помощью команды s = open(‘files/24-263.txt’).readline(). Заведем переменную m, изначально равную 10000, предполагая, что ответ на задачу будет меньше этого значения, переменная будет использоваться для хранения минимальной длины подстроки, в которой символ Z встречается не менее 120 раз.
Создадим цикл, который будет перебирать все возможные левые границы подстроки, начиная с первого символа и до последнего. Внутренний цикл будет проверять все возможные правые границы подстроки. Вложенный цикл по правым границам подстроки идет от l + m до l (включая l + m, но не включая l), причем правый индекс r уменьшается на единицу на каждом шаге. Это значит, что правый индекс двигается влево от предполагаемой правой границы подстроки, начиная с самого дальнего значения. Внутри вложенного цикла извлекаем подстроку c из строки s, которая начинается с индекса l и заканчивается индексом r включительно. Метод с.count(‘Z’) возвращает количество вхождений символа ‘Z’ в подстроке, и если в подстроке c появляется больше 120 символов ‘Z’, то выполняется следующий шаг — программа обновляет значение m — ему соответствует минимальное значение между текущим значением m и длиной текущей подстроки len(с). Если условие не выполняется, то внутренний цикл прерывается с помощью оператора break.
После завершения всех циклов программа выводит m — минимальную длину подстроки, в которой символ Z встречается не менее 120 раз.
s = open(‘files/24-263.txt’).readline()
m = 10000
for l in range(len(s)):
for r in range(l+m,l,-1):
c = s[l:r+1]
if c.count(‘Z’)>=120: m = min(m,len(c))
else: break
print(m)
Ответ: 2310
Может возникнуть вопрос, почему не появляется ошибки при выходе за границы строки во внутреннем цикле. Рассмотрим на примере, возьмем строку s = ‘12345’, если попытаться вывести срез из 10 символов (s[10]), то ошибка будет. Но при этом, если выводить срез, начиная с того символа, индекс которого в строке есть, ошибка не появится, и программа выведет символы начиная с указанного и до конца строки:
Задача №6
Текстовый файл 24-293.txt состоит не более чем из 106 символов и содержит только заглавные буквы латинского алфавита и десятичные цифры. Найдите максимальную длину подстроки, которая содержит ровно 100 символов D, не содержит цифр, и не содержит сочетаний символов DS и SD.
Решение
Сохраним файл 24-293.txt и считаем его, преобразовав в строку с помощью команды s = open(‘files/24-293.txt’).readline(). Заменим в строке s все цифры (‘123456789’) на «0» с помощью функции replace(). Заведем переменную m, изначально равную нулю, она будет использоваться для хранения максимальной длины подстроки. Создадим цикл, который будет перебирать все возможные левые границы подстроки, начиная с первого символа и до последнего. Внутренний цикл будет проверять все возможные правые границы подстроки. Правый индекс начинается с l + m, где m — это текущий максимум длины подстроки. Внутри вложенного цикла извлекаем подстроку c из строки s, которая начинается с индекса l и заканчивается индексом r включительно. Проверяем условия для подстроки c: если она содержит ноль, или в ней более 100 символов ‘D’, или она содержит сочетания символов DS и SD, то программа прерывается с помощью оператора break. Если же подстрока соответствует условию задачи, то есть в ней содержится ровно 100 символов ‘D’ и нет цифр и запрещенных сочетаний, то программа продолжает проверку подстроки и обновляет значение переменной m — ему соответствует максимальное значение между текущим значением m и длиной текущей подстроки.
После завершения всех циклов программа выводит максимальную длину подстроки, которая удовлетворяет условиям задачи.
s = open(‘files/24-293.txt’).readline()
for c in ‘123456789’: s = s.replace(c,’0′)
m = 0
for l in range(len(s)):
for r in range(l+m,len(s)):
c = s[l:r+1]
if ‘0’ in c or c.count(‘D’)>100 or ‘DS’ in c or ‘SD’ in c:
break
elif c.count(‘D’)==100: m = max(m, len(c))
print(m)
Ответ: 644
Задача № 7
Текстовый файл состоит не более чем из 106 символов X, Y и Z. Определите максимальное количество идущих подряд символов, среди которых каждые два соседних различны. Для выполнения этого задания следует написать программу.
Файлы к заданию: 24.txt
Решение
Сохраним файл 24_21.txt и считаем его, преобразовав в строку с помощью команды s = open(‘files/24_21.txt’).readline(). Заведем переменную m, изначально равную нулю, она будет использоваться для хранения максимальной длины подстроки. Создадим цикл, который будет перебирать все возможные левые границы подстроки, начиная с первого символа и до последнего. Внутренний цикл будет проверять все возможные правые границы подстроки. Правый индекс начинается с l + m, где m — это текущий максимум длины подстроки. Внутри вложенного цикла извлекаем подстроку c из строки s, которая начинается с индекса l и заканчивается индексом r включительно. Проверяем условия для подстроки c: строка не должна содержать двух одинаковых символов подряд, в нашем случае, так строка состоит всего из трех различных символов, можно проверять, что в строке с не содержится пар ‘XX’ или ‘YY’ или ‘ZZ (#if ‘XX’ not in c and ‘YY’ not in c and ‘ZZ’ not in c)’. Либо можно проверять, что все соседние символы различны, в цикле с первого до предпоследнего элемента проверяется неравенство текущего и следующего символов (if all(c[i]!=c[i+1] for i in range(len(c)-1))). Но код, подходящий для общего случая, выглядит так: if all(x!=y for x,y in zip(c,c[1:])) — используется функция zip, которая создает пары соседних символов из строки c, проверяем, что все такие пары имеют разные элементы.
Если подстрока соответствует условию задачи, то программа продолжает проверку подстроки и обновляет значение переменной m — ему соответствует максимальное значение между текущим значением m и длиной текущей подстроки. Если условие не выполняется, то внутренний цикл прерывается с помощью оператора break.
После завершения всех циклов программа выводит максимальную длину подстроки, которая удовлетворяет условиям задачи.
s = open(‘files/24_21.txt’).readline()
m = 0
for l in range(len(s)):
for r in range(l+m,len(s)):
c = s[l:r+1]
#if ‘XX’ not in c and ‘YY’ not in c and ‘ZZ’ not in c:
#if all(c[i]!=c[i+1] for i in range(len(c)-1)):
if all(x!=y for x,y in zip(c,c[1:])):
m = max(m,len(c))
else:
break
print(m)
Ответ: 35
Задача №8
Текстовый файл 24-204.txt содержит строку из заглавных латинских букв A, B и C, всего не более чем из 106 символов. Найдите максимальное количество подряд идущих пар символов AA или CC. Искомая подстрока может включать только пары АA, только пары CС или содержать одновременно как пары АA, так и пары CC.
Решение
Сохраним файл 24204.txt и считаем его, преобразовав в строку с помощью команды s = open(‘files/24-204.txt’).readline(). Заведем переменную m, изначально равную нулю, она будет использоваться для хранения максимальной длины подстроки. Создадим цикл, который будет перебирать все возможные левые границы подстроки, начиная с первого символа и до последнего. Внутренний цикл будет проверять все возможные правые границы подстроки. Правый индекс начинается с l + m, где m — это текущий максимум длины подстроки. Внутри вложенного цикла извлекаем подстроку c из строки s, которая начинается с индекса l и заканчивается индексом r включительно. Проверяем, что длина подстроки c является четной. Это необходимо, так как мы будем работать с парами символов. Далее проверяем, что каждая пара символов (взятая с шагом 2) из подстроки c может быть либо «AA», либо «CC». Генератор all() перебирает все возможные индексы с шагом 2 (начиная с 0) и проверяет, что каждая пара символов (например, c[i] + c[i+1]) находится в списке [‘AA’, ‘CC’]. Если все пары удовлетворяют этому условию, программа продолжает проверку. Если подстрока удовлетворяет всем условиям, программа обновляет переменную m, чтобы сохранить максимальную длину такой подстроки. В противном случае, программа прерывает внутренний цикл с помощью оператора break. Это позволяет избежать дальнейших проверок для текущей правой границы. После завершения всех циклов программа выводит максимальную длину подстроки, но делит её на 2 (поскольку длина подстроки должна быть четной, и каждая пара символов учитывается как 1 единица длины).
s = open(‘files/24-204.txt’).readline()
m = 0
for l in range(len(s)):
for r in range(l+m,len(s)):
c = s[l:r+1]
if len(c)%2==0:
if all(c[i]+c[i+1] in [‘AA’,’CC’]
for i in range(0,len(c),2)):
m = max(m,len(c))
else:
break
print(m//2)
Ответ: 1310
Задача №9
Текстовый файл 24-197.txt содержит строку из заглавных латинских букв X, Y и Z, всего не более чем из 106 символов. Определите максимальное количество идущих подряд троек символов X*Y или Z*Y, где * обозначает один любой символ.
Решение
Сохраним файл 24-197.txt и считаем его, преобразовав в строку с помощью команды s = open(‘files/24-197.txt’).readline(). Заведем переменную m, изначально равную нулю, она будет использоваться для хранения максимальной длины подстроки. Создадим цикл, который будет перебирать все возможные левые границы подстроки, начиная с первого символа и до последнего. Внутренний цикл будет проверять все возможные правые границы подстроки. Правый индекс начинается с l + m, где m — это текущий максимум длины подстроки. Внутри вложенного цикла извлекаем подстроку c из строки s, которая начинается с индекса l и заканчивается индексом r включительно. Проверяем, что длина подстроки c является кратной 3. Это необходимо, чтобы подстрока могла быть разделена на тройки символов. Далее проверяем, что каждый блок из трех символов в подстроке удовлетворяет условию «X*Y» или «Z*Y», где символ на позиции i – это X или Z, а на пощиции i+1 (третий символ блока) — это «Y». Если это условие выполняется для всей подстроки, значит подстрока состоит только из идущих подряд троек символов X*Y или Z*Y. В этом случае обновляем переменную m, чтобы сохранить максимальную длину такой подстроки. Если подстрока не удовлетворяет условию, программа прерывает внутренний цикл с помощью оператора break. Это позволяет избежать дальнейших проверок для текущей правой границы. После завершения всех циклов программа выводит максимальную длину подстроки, деленную на 3. Деление на 3 необходимо, так как в ответе требуется указать количество идущих подряд троек символов.
s = open(‘files/24-197.txt’).readline()
m = 0
for l in range(len(s)):
for r in range(l+m,len(s)):
c = s[l:r+1]
if len(c)%3==0:
if all(c[i]+c[i+2] in [‘XY’,’ZY’]
for i in range(0,len(c),3)):
m = max(m,len(c))
else:
break
print(m//3)
Ответ: 20
Задача №10
Текстовый файл 24-s2.txt состоит не более чем из 106 заглавных латинских букв. Определите символ, который чаще всего встречается в файле сразу после буквы X. В ответе запишите сначала этот символ, а потом сразу (без разделителя) сколько раз он встретился после буквы X. Если таких символов несколько, нужно вывести тот, который стоит раньше в алфавите. Например, в тексте XBCXXBXDDD после буквы X два раза стоит B, по одному разу – X и D. Для этого текста ответом будет B2.
Решение
Нам нужно подсчитать, сколько раз каждый символ встречается после буквы ‘X’, это можно сделать с помощью 26 (количество букв латинского алфавита) счетчиков, но это абсолютно нерационально. Гораздо эффективнее – создать и использовать частотный словарь, ключом в котором будет буквенный символ, а значением – количество этих символов:
Сохраним файл 24-s2.txt и считаем его, преобразовав в строку с помощью команды s = open(‘files/24-s2.txt’).readline(). Создаем словарь d, где ключи — это все заглавные латинские буквы (от ‘A’ до ‘Z’), а значения инициализируются как 0. Этот словарь будет использоваться для подсчета, сколько раз каждая буква встречается после буквы ‘A’ в строке. Пишем цикл, в котором перебираем все соседние символы в строке s с помощью функции zip(s, s[1:]). Функция zip создает пары, где c1 — это текущий символ, а c2 — следующий символ в строке. Если текущий символ c1 равен ‘Х’, то увеличиваем значение в словаре d для символа c2 (следующего символа). Это означает, что мы считаем, сколько раз после буквы ‘Х’ в строке встречается каждая другая буква.
Если мы хотим посмотреть, что будет в нашем словаре после выполнения цикла, можно вывести его на экран:
Мы видим, сколько раз встречается каждая буква после буквы Х:
Можно так же вывести только значения из словаря d, без ключей, с помощью команды
Получили список чисел:
Можно вывести только ключи (в нашем случае – буквы латинского алфавита) из словаря d:
Находим максимальное значение в словаре d, которое будет означать, сколько раз после буквы ‘Х’ встречалась наиболее частая буква. Выводим максимальное значение m (сколько раз встречалась наиболее частая буква после ‘Х’), а также список всех букв, которые встречаются после ‘Х’ максимальное количество раз. Для этого перебираем в цикле все буквы, для которых значение в словаре равно максимальному.
s = open(‘files/24-s2.txt’).readline()
d = {x:0 for x in ‘QWERTYUIOPLKJHGFDSAZXCVBNM’}
for c1, c2 in zip(s,s[1:]):
if c1==’X’:
d[c2] += 1
m = max(d.values())
print(m,[c for c in d if d[c]==m])
Ответ: U1618
Задача №11
Текстовый файл 24-157.txt состоит не более чем из 106 символов и содержит только заглавные буквы латинского алфавита (ABC…Z). Определите символ, который чаще всего встречается в файле между двумя одинаковыми символами. Например, в тексте CCBAABABCBC есть комбинации ABA, BAB, BCB и CBC. Чаще всего – 2 раза – между двумя одинаковыми символами стоит B, в ответе для этого случая надо написать B2 (без пробелов и других разделителей). Если таких символов несколько, выведите тот, который стоит раньше в алфавите.
Решение
Сохраним файл 24-157.txt и считаем его, преобразовав в строку с помощью команды s = open(‘files/24-157.txt’).readline(). Создаем словарь d, где ключами являются все заглавные латинские буквы (от ‘A’ до ‘Z’), а значениями инициализируются как 0. Этот словарь будет использоваться для подсчета количества вхождений каждой буквы в определенных условиях. Пишем цикл, в котором перебираем все соседние символы в строке s с помощью функции zip(s,s[1:],s[2:]). Эта функция создает три последовательности: первую — с символами строки s, вторую — с символами строки, начиная с первого индекса, и третью — с символами, начиная со второго индекса. Таким образом, она получает тройки символов, которые будут представлять собой комбинации соседних символов. Если первый символ в тройке равен третьему, то увеличиваем счетчик для второго символа (то есть c2) в словаре d. После того как программа посчитает все вхождения символов, она находит максимальное количество повторений для символа, который оказался между одинаковыми символами. В завершении программы выводим максимальное количество повторений символа между одинаковыми буквами (m), а также все символы, которые встречаются m раз.
s = open(‘files/24-157.txt’).readline()
d = {x:0 for x in ‘QWERTYUIOPLKJHGFDSAZXCVBNM’}
for c1,c2,c3 in zip(s,s[1:],s[2:]):
if c1==c3:
d[c2] += 1
m = max(d.values())
print(m,[c for c in d if d[c]==m])
Ответ: W1608