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

24. Подсчет символов: Определите в прилагаемом файле максимальное количество идущих подряд…

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

Текстовый файл состоит из десятичных цифр и заглавных букв латинского алфавита. Определите в прилагаемом файле максимальное количество идущих подряд символов, среди которых подстрока $2025$ встречается не менее $90$ раз и при этом содержится ровно $80$ букв $Y$.

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

Условий два, и они ведут себя по-разному. «Ровно $80$ букв $Y$» — жёсткое, оно и ограничивает окно. «Не менее $90$ вхождений $2025$» — монотонное: при расширении окна вхождений только прибавляется, поэтому оно нам не мешает растягиваться.

Раз букв $Y$ ровно $80$, окно содержит какой-то отрезок из $80$ подряд идущих $Y$: с номерами от $i$ до $i+79$. Перебираем $i$. Влево окно можно тянуть до предыдущей буквы $Y$ (не включая её), вправо — до следующей буквы $Y$ (не включая). Это и даёт максимальное окно для данного $i$: ещё один шаг в любую сторону захватит $81$-ю букву $Y$.

Осталось проверить вхождения $2025$. Поскольку окно уже растянуто до предела, если здесь их меньше $90$, то при этом $i$ вариантов нет вовсе. Считать удобно по списку позиций вхождений: нужны те, что начинаются не левее $L$ и целиком помещаются до $R$, то есть начало не правее $R-3$.

import bisect

s = open('24-06.txt').read().strip()
n = len(s)

y = [i for i, c in enumerate(s) if c == 'Y']
starts = []                                # позиции начал подстроки 2025
p = s.find('2025')
while p != -1:
    starts.append(p)
    p = s.find('2025', p + 1)

m = len(y)
best = 0
for i in range(m - 79):                    # окно содержит Y с номерами i..i+79
    L = y[i-1] + 1 if i > 0 else 0         # упираемся в предыдущую Y
    R = y[i+80] - 1 if i + 80 < m else n-1 # упираемся в следующую Y

    lo = bisect.bisect_left(starts, L)
    hi = bisect.bisect_right(starts, R - 3)  # вхождение должно влезть целиком
    if hi - lo >= 90:
        best = max(best, R - L + 1)

print(best)   # 2981

Проверка найденного окна: длина $2981$, букв $Y$ ровно $80$, вхождений $2025$ — $656$, то есть не менее $90$. Слева и справа от окна стоят буквы $Y$ — расширить нельзя.

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

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