24. Подсчет символов: Определите в прилагаемом файле максимальное количество идущих подряд…
Текстовый файл состоит из десятичных цифр и заглавных букв латинского алфавита. Определите в прилагаемом файле максимальное количество идущих подряд символов, оканчивающихся подстрокой $2025$, среди которых буква $Y$ встречается не менее $140$ раз, а подстрока $2025$ содержится ровно $50$ раз.
В ответе запишите число – количество символов в найденной последовательности. Для выполнения этого задания следует написать программу.
Ключевое упрощение даёт условие «оканчивается подстрокой $2025$»: правая граница окна не произвольна, это конец какого-то вхождения $2025$. Перебираем вхождения: пусть $j$-е вхождение последнее в окне, тогда правая граница $R = occ[j] + 3$.
Дальше работает условие «ровно $50$ раз». Раз последнее вхождение имеет номер $j$, то первое обязано иметь номер $j-49$. Значит вхождение с номером $j-50$ в окно попасть не должно, и левая граница может опуститься максимум до $L = occ[j-50] + 1$. Так мы берём самое длинное окно для данного $j$.
Условие на букву $Y$ — «не менее $140$», оно монотонно: при расширении окна букв $Y$ только прибавляется. Поэтому проверять его достаточно один раз, уже на максимально растянутом окне: если и там $Y$ меньше $140$, то никакое более короткое окно с тем же $j$ не подойдёт.
Подстрока $2025$ сама с собой не пересекается, поэтому позиции вхождений просто собираются через find.
s = open('24-04.txt').read().strip()
occ = [] # позиции начал подстроки 2025
p = s.find('2025')
while p != -1:
occ.append(p)
p = s.find('2025', p + 1)
py = [0] * (len(s) + 1) # префиксные суммы по буквам Y
for i, c in enumerate(s):
py[i+1] = py[i] + (c == 'Y')
best = 0
for j in range(49, len(occ)): # j-е вхождение — последнее в окне
R = occ[j] + 3 # +3 — окно кончается на 2025
L = occ[j-50] + 1 if j >= 50 else 0 # не пускаем внутрь 51-е вхождение
if py[R+1] - py[L] >= 140:
best = max(best, R - L + 1)
print(best) # 938
Проверка найденного окна: длина $938$, последние четыре символа — $2025$, вхождений $2025$ ровно $50$, букв $Y$ — $237$, то есть не менее $140$.