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

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

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

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

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

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