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

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

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

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

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

Здесь два условия разного типа: «не менее $110$» — монотонное (от расширения окна только улучшается), а «ровно $90$» — нет. Поэтому опираемся на второе: любое подходящее окно содержит ровно $90$ подряд идущих букв $W$, то есть отрезок $W$ с номерами от $i$ до $i+89$. Значит левая граница лежит между предыдущей буквой $W$ и $w[i]$, а правая — между $w[i+89]$ и следующей буквой $W$. Перебираем $i$, и внутри каждого такого «коридора» ищем самое короткое окно, где вхождений $2025$ набирается $110$.

Внутри коридора левую границу выгодно брать как можно правее, а правую — как можно левее. Двигаем $L$ по позициям вхождений $2025$ в его допустимом диапазоне: чем левее $L$, тем раньше начинается блок из $110$ вхождений и тем меньше можно взять $R$. Для каждого $L$ правая граница равна максимуму из конца $110$-го вхождения и позиции $w[i+89]$ — обе границы обязаны выполняться одновременно.

Подстрока $2025$ сама с собой не пересекается, поэтому вхождения можно просто собрать в список позиций через $find$.

import bisect

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

occ = []                                   # позиции начал подстроки 2025
p = s.find('2025')
while p != -1:
    occ.append(p)
    p = s.find('2025', p + 1)

w = [i for i, ch in enumerate(s) if ch == 'W']
m, K = len(w), len(occ)
best = float('inf')

for i in range(m - 89):                    # окно содержит W с номерами i..i+89
    loL = w[i-1] + 1 if i > 0 else 0       # левее нельзя: захватим 91-ю W
    hiL = w[i]
    loR = w[i+89]
    hiR = w[i+90] - 1 if i + 90 < m else n - 1

    kw = bisect.bisect_left(occ, hiL)
    kmin = bisect.bisect_left(occ, loL)
    for k in range(kw, kmin - 1, -1):      # k — номер первого вхождения в окне
        if k + 109 >= K:
            continue
        L = min(hiL, occ[k]) if k < K else hiL
        if L < loL:
            break
        R = max(occ[k+109] + 3, loR)       # +3 — последний символ 110-го вхождения
        if R <= hiR:
            best = min(best, R - L + 1)

print(best)   # 780

Проверка найденного окна: длина $780$, букв $W$ ровно $90$, вхождений $2025$ ровно $110$.

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

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