Дошкольникам
1 класс
2 класс
3 класс
4 класс
5 класс
6 класс
7 класс
8 класс
9 класс
10 класс
11 класс
ОГЭ
ЕГЭ
ВУЗ
Для всех
Назад

24. Подсчет символов: Текстовый файл состоит из заглавных букв латинского алфавита A, B, C, D, E и…

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

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

В ответе запишите число – количество символов в найденной последовательности. Для выполнения этого задания следует написать программу.

Соберём позиции всех вхождений пары $BC$ — это индексы, где стоит $B$, а следом $C$. Пара считается попавшей в окно, только если внутри оба её символа: начало не левее $L$ и не правее $R-1$.

Пусть в окно попали вхождения с номерами от $i$ до $i+189$, то есть ровно $190$ штук. Тогда вхождение с номером $i-1$ внутрь попасть не должно, значит левую границу опускаем максимум до $occ[i-1]+1$. А вхождение с номером $i+190$ не должно поместиться целиком, значит правую границу тянем до $occ[i+190]$: сама буква $B$ этой пары в окно попасть может, лишь бы не попала её $C$.

s = open('24-13.txt').read().strip()
n = len(s)
K = 190

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

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)   # 2287

Проверка найденного окна: длина $2287$, вхождений $BC$ ровно $190$. Слева от окна стоит $B$, а первый символ окна — $C$, то есть шаг влево добавил бы $191$-е вхождение. Справа от окна стоит $C$, а последний символ окна — $B$, то есть шаг вправо тоже добавил бы вхождение. Растянуть некуда.

Тот же ответ даёт метод двух указателей: ведём правую границу вперёд, подтягиваем левую, пока вхождений больше $190$, и запоминаем длину в моменты, когда их ровно $190$. На файле в $10$ миллионов символов он заметно медленнее, но удобен как независимая проверка.

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

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