Question

Текстовый файл состоит не более чем из $10^6$ символов латинского алфавита. Определите минимальную длину подстроки, содержащей ровно 110 символов `U`. Для выполнения этого задания следует написать программу.

Accepted Answer

1765

Answer

Идея решения: найти все позиции символа `U` в строке, затем для каждого окна из 110 символов `U` вычислить длину подстроки между первым и последним символом в окне.

Алгоритм:
1. Прочитаем содержимое файла.
2. Соберём все индексы, где встречается символ `U`.
3. Переберём все окна размером 110 символов `U` (от позиции $j$ до позиции $j + 109$ в массиве индексов).
4. Для каждого окна вычислим длину подстроки: разность между индексом последнего и первого символа `U` плюс 1.
5. Найдём минимальную длину среди всех окон.

```python
f = open('24.txt')
s = f.readline()

pos = []
for i in range(len(s)):
    if s[i] == 'U':
        pos.append(i)

mini = 10**10
for j in range(len(pos) - 109):
    length = pos[j + 109] - pos[j] + 1
    mini = min(mini, length)

print(mini)
```

Пояснение: массив `pos` содержит индексы всех символов `U`. Для каждого окна из 110 символов `U` (начиная с индекса $j$ и заканчивая индексом $j + 109$ в массиве `pos`) длина подстроки равна `pos[j + 109] - pos[j] + 1`. Перебираем все такие окна и отслеживаем минимум.

Задание №24ПрограммированиеЕГЭ по информатике