Задание высокого уровня сложности, проверяющее умение создавать программы для обработки символьной информации. На его выполнение отводится 18 минут. К заданию прилагается текстовый файл. Необходимо определить максимальное количество идущих подряд символов, среди которых символ «Т» встречается ровно 100 раз.
Моделирование на примере
Рассмотрим упрощенную задачу: найти непрерывную подпоследовательность, содержащую ровно три символа «Т». Возьмем строку: «ТТТwxaYТ». Индексы символов: 0, 1, 2, 3, 4, 5, 6, 7, 8.
Найдем все индексы символа «Т»: 0, 6. Длина подпоследовательности между этими символами «Т»: 8 — 0 = 8. Так как символ «Т» с индексом 0 входит в подпоследовательность, вычитаем 1: 8 — 1 = 7. Проверим: в подпоследовательности «ТТТwxaYТ» три символа «Т». Длина подпоследовательности: 7 символов.
В общем случае, для поиска подпоследовательности с ровно 100 символами «Т», нужно сравнивать индекс текущего символа «Т» (i) с индексом символа «Т», находящегося на расстоянии 101 позиции (i + 101). Разница между этими индексами, минус 1, и будет длиной подпоследовательности.
Возможные сложности и решение
Может возникнуть ситуация, когда между двумя символами «Т» находятся другие символы, отличные от «Т». Например, добавим символы «VXYZ» между символами «Т»: «ТТТwxaYТVXYZ». Предложенный алгоритм корректно определит подпоследовательность «ТТТwxaYТ», но максимальная подпоследовательность может быть больше. Для решения задачи в общем случае требуется более сложный алгоритм, например, с использованием сдвижного окна или динамического программирования. Однако, в демоверсии 2024 года текстовый файл содержит одну длинную строку, которая начинается и заканчивается символом «Т», что позволяет использовать упрощенный алгоритм.
Алгоритм решения для демоверсии
- Чтение файла: Используем функцию open() для чтения текстового файла, находящегося в той же директории, что и скрипт Python.
- Чтение строки: Метод readline() читает всю строку из файла и сохраняет её в переменную S.
- Поиск индексов «Т»: Создаем список T, содержащий индексы всех символов «Т» в строке S. Проходим циклом по строке S и если символ равен «Т», добавляем его индекс в список T.
- Поиск максимальной подпоследовательности: Используем функцию max() для нахождения максимальной длины подпоследовательности. Цикл перебирает элементы списка T и вычисляет длину подпоследовательности между элементами T[i] и T[i + 100] по формуле: T[i + 100] — T[i] — 1.
Результаты
Запуск алгоритма на файле из демоверсии дает ответ: 133.
Рассмотренный алгоритм эффективно решает 24-е задание демоверсии ЕГЭ по информатике 2024 года, учитывая специфику структуры данных в файле демоверсии. Ключевыми моментами являются корректное чтение файла, поиск индексов символа «Т» и вычисление длины подпоследовательности. Для решения задачи в общем случае необходим более универсальный подход.