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

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

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

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

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

Здесь ищется минимум, и это заметно упрощает задачу по сравнению с максимумом. Соберём позиции всех вхождений пары $AB$ — индексы, где стоит $A$, а следом $B$.

Пусть в окно попали вхождения с номерами от $i$ до $i+219$, то есть ровно $220$ штук. Сжимаем окно с обеих сторон до упора. Слева упираемся в самое первое из них: левая граница равна $occ[i]$, дальше двигаться нельзя, потеряем вхождение. Справа упираемся в последнее: правая граница равна $occ[i+219]+1$, потому что в окно должна войти и вторая буква пары, то есть $B$.

Никаких дополнительных проверок не нужно. Окно начинается с $A$ и кончается на $B$, значит соседние вхождения с номерами $i-1$ и $i+220$ внутрь заведомо не попадают — мы взяли ровно минимальный отрезок, накрывающий нужные $220$ пар.

s = open('24-20.txt').read().strip()
n = len(s)
K = 220

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

best = float('inf')
for i in range(m - K + 1):        # occ[i..i+K-1] — вхождения внутри окна
    L = occ[i]                    # начинаем прямо с первого вхождения
    R = occ[i+K-1] + 1            # кончаем на второй букве последнего
    best = min(best, R - L + 1)

print(best)   # 1088

Проверка найденного окна: длина $1088$, вхождений $AB$ ровно $220$, начинается оно с $AB$ и кончается на $AB$. Сжать сильнее нельзя — любой шаг внутрь разрушит крайнюю пару.

Обратите внимание на разницу с задачами на максимум. Там границы упирались в соседние лишние вхождения и требовался сдвиг на единицу ($occ[i-1]+1$ слева и $occ[i+K]$ справа). Здесь всё наоборот: границы упираются в свои же крайние вхождения. Единственное, о чём легко забыть, — прибавить $1$ к правой границе, чтобы захватить букву $B$ последней пары.

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

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