Каждый год на ЕГЭ по информатике ученики спотыкаются об 24-ю задачу.
Файл из тысяч символов, условия с подстроками, счётчиками… Кажется, что это решают только гении.
На самом деле, если знать приём «скользящего окна», задача становится понятной даже десятикласснику.
Сейчас покажу на примерах.
Сама задача (2025 + Y)
Текстовый файл состоит из десятичных цифр и заглавных латинских букв.
Определите максимальное количество идущих подряд символов, среди которых
– подстрока 2025 встречается не менее 90 раз
– и содержится ровно 80 букв Y
В ответ запишите количество символов в найденной последовательности.
Почему перебор не работает
Если пытаться проверять каждую возможную подстроку, это будут миллионы вариантов — программа работает часами.
Нужен более «умный» способ — скользящее окно (или «два указателя»): мы идём по строке один раз, обновляя счётчики.
Учимся на маленьком примере
Пусть строка:
2025Y20252025Y2025
Нужно найти кусок, где 2025 ≥2 раз и Y ровно 1 раз.
Алгоритм:
- начинаем с левого конца;
- двигаем правый указатель, увеличиваем счётчики (сколько Y и сколько 2025);
- если Y стало больше 1 — двигаем левый указатель, убираем старые символы;
- если условия выполняются — фиксируем длину окна.
Так мы всегда храним только один кусок строки, а не перебираем миллионы.
Пошаговый алгоритм
- Читаем файл.
- Создаём массив признаков is2025 — где начинается подстрока 2025.
- Идём по строке правым указателем:
– если текущий символ Y — увеличиваем cnt_y;
– если на позиции right-3 начинается 2025 — увеличиваем cnt_2025. - Двигаем левый указатель, пока условий слишком много (больше 80 Y).
- Если условия выполнены — обновляем максимум длины.
Рассмотрим алгоритм на коде
Комментарии:
- is2025 нужен, чтобы не искать 2025 каждый раз заново.
- Сдвигаем левую границу окна, чтобы количество Y всегда ≤80.
- Проверяем условие, когда cnt_y == 80 и cnt_2025 >= 90.
Ответ:
Как получить ответ
Возьмите реальный файл 24.txt (он лежит вместе с вариантом КИМ на сайте ФИПИ или в тренажёре).
Сохраните код в .py-файл, положите рядом 24.txt и запустите Python.
Программа выведет одно число — это и есть ответ для этой задачи.
Ошибки, которые могут вылезти при верном коде:
Далеко не всегда в таких задачах ошибки в коде. Все беды могут быть лишь из-за одной строчки кода. И это чтение файла. Почему же?
Неверный путь до файла или же неверное название файла --> Получаем ошибку
Решение:
- Всегда проверяйте директорию файла и его название. Если файл называется, например, 24_327832.txt, переименуйте его в 24.txt для избежания ошибок в написании путя до файла. Однако при копировании названия файла такую ошибку не допустить, но все же.
- Никогда не забывайте писать формат файла после его названия:
C://Users/ki220/Downloads/24.txt - Корректный пример путя до файла для верного считывания данных
C://Users/ki220/Downloads/24 - Неверно, так мы не сможем получить данные из файла и получим лишь ошибку
А если хотите знать больше тонкостей при подготовке к экзамену и быть начеку всех новостей - переходите в мой телеграмм канал, где я публикую новые варианты, разборы заданий и статей, которые будут полезны абитуриенту