24. Подсчет символов: Определите в прилагаемом файле максимальное количество идущих подряд…
Текстовый файл состоит из десятичных цифр и заглавных букв латинского алфавита. Определите в прилагаемом файле максимальное количество идущих подряд символов, среди которых подстрока $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$ — расширить нельзя.