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

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

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

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

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

Условие «не более $110$» монотонно в другую сторону, чем привычное «не менее»: чем шире окно, тем больше вхождений, значит ограничение работает как потолок и само задаёт границы. Никаких «ровно» здесь нет, поэтому задача решается напрямую.

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

Дальше рассуждаем так. Пусть в окно попали вхождения с номерами от $i$ до $i+109$ (ровно $110$ штук — брать меньше невыгодно, окно только сузится). Тогда предыдущее вхождение с номером $i-1$ внутрь попасть не должно, значит левую границу можно опустить максимум до $occ[i-1]+1$. А вхождение с номером $i+110$ не должно поместиться целиком, значит правая граница дотягивается максимум до $occ[i+110]$ — сама буква $A$ этой пары в окно попасть может, лишь бы не попала её $B$.

Отдельно стоит помнить про край: если всего вхождений не больше $110$, ответ — вся длина файла.

s = open('24-11.txt').read().strip()
n = len(s)
K = 110

occ = [i for i in range(n-1) if s[i] == 'A' and s[i+1] == 'B']
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 # 111-е вхождение не должно влезть целиком
        best = max(best, R - L + 1)
    print(best)   # 628

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

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

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