Подготовка к школе
1 класс
2 класс
3 класс
4 класс
5 класс
6 класс
7 класс
8 класс
9 класс
10 класс
11 класс
ОГЭ
ЕГЭ
Для всех
Назад

24. Подсчет символов: #297628

Сообщить о проблеме
Задание #297628
Задание было решено верно
Задание было решено неверно

Текстовый файл состоит из заглавных букв латинского алфавита $A$, $B$, $C$, $D$, $E$ и $F$. Определите максимальное количество идущих подряд символов в прилагаемом файле, среди которых пара символов $DE$ (в указанном порядке) встречается не более $240$ раз.

Для выполнения этого задания следует написать программу.

Это крайний случай, ради которого в решении стоит отдельная проверка. Буква $D$ встречается в файле всего $629$ раз при общей длине почти в миллион символов, а пара $DE$ — лишь $38$ раз, что заметно меньше разрешённых $240$. Значит ограничение не нарушается нигде, и подходящим фрагментом оказывается весь файл целиком. Ответ равен его длине.

Общая схема при этом остаётся прежней. Соберём позиции всех вхождений пары $DE$ — индексы, где стоит $D$, а следом $E$. Пара попадает в окно, только если внутри оба её символа: начало не левее $L$ и не правее $R-1$. Если вхождений больше $240$, пусть в окно попали те, что имеют номера от $i$ до $i+239$. Тогда предыдущее вхождение внутрь попасть не должно, и левая граница опускается до $occ[i-1]+1$, а следующее не должно поместиться целиком, и правая граница дотягивается до $occ[i+240]$.

s = open('24-25.txt').read().strip()
n = len(s)
K = 240

occ = [i for i in range(n-1) if s[i] == 'D' and s[i+1] == 'E']
m = len(occ)

if m <= K:                                 # ограничение нигде не нарушается
    print(n)
else:
    best = 0
    for i in range(m - K + 1):             # occ[i..i+K-1] — вхождения внутри окна
        L = occ[i-1] + 1 if i > 0 else 0   # предыдущее вхождение отсекаем
        R = occ[i+K] if i + K < m else n-1 # следующее не должно влезть целиком
        best = max(best, R - L + 1)
    print(best)

# 970249

Метод двух указателей на том же файле даёт то же самое число, что подтверждает вывод.

Здесь стоит быть внимательным с двумя вещами. Во-первых, если в программе не предусмотрена ветка для случая, когда вхождений мало, цикл окажется пустым и напечатает ноль. Полезно сразу после сбора позиций посмотреть, сколько их вообще получилось, и сверить с порогом из условия: $38$ против $240$ — разница очевидная. Во-вторых, раз ответом идёт длина всего файла, критично не захватить лишний символ. Перевода строки в конце этого файла нет, но .strip() при чтении лучше ставить всегда.

Показать
Очки опыта 20
Спросить Зави
0 заданий сегодня

Предложить улучшение