Задание 24 ЕГЭ по информатике · D6DFE2
Подстрока и буквы: мин./макс. длинаВысокаяКЭС 3.9
Задание выполняется с использованием прилагаемых файлов.
Текстовый файл состоит из десятичных цифр и заглавных букв латинского алфавита. Определите в прилагаемом файле максимальное количество идущих подряд символов, среди которых подстрока 2025 встречается не менее 90 раз и при этом содержится ровно 80 букв Y.
В ответе запишите число – количество символов в найденной последовательности.
Для выполнения этого задания следует написать программу.
4_24_D6DFe2.txtТекстовый файл состоит из десятичных цифр и заглавных букв латинского алфавита. Определите в прилагаемом файле максимальное количество идущих подряд символов, среди которых подстрока 2025 встречается не менее 90 раз и при этом содержится ровно 80 букв Y.
В ответе запишите число – количество символов в найденной последовательности.
Для выполнения этого задания следует написать программу.
Показать ответ
2981
Подсказки (3)
- Рассматривайте все непрерывные фрагменты файла и поддерживайте количество вхождений подстроки 2025 и букв Y.
- Для фиксированной левой границы расширяйте правую границу, пока число букв Y не превысит 80, а затем ищите самый длинный допустимый фрагмент.
- Удобно использовать два указателя и префиксные суммы: отдельно для букв Y и для позиций, с которых начинается подстрока 2025.
Решение
1. Считаем позиции начала всех вхождений подстроки 2025. Вхождения могут пересекаться, поэтому проверяем каждую позицию строки. 2. Построим префиксные суммы количества букв Y и количества вхождений 2025. Для фрагмента [l, r] число букв Y вычисляется за O(1). 3. При помощи двух указателей перебираем максимальные фрагменты, содержащие ровно 80 букв Y. Для каждого такого фрагмента проверяем, что количество вхождений 2025 не менее 90, и обновляем максимум длины.
Частые ошибки
- Считать только непересекающиеся вхождения подстроки 2025.
- Проверять количество букв Y во всём файле, а не в текущем фрагменте.
- Не учитывать, что искомая последовательность может начинаться или заканчиваться внутри области между двумя вхождениями 2025.
- Пытаться получить численный ответ по скриншоту интерфейса без самого файла.
Источник: Открытый банк ФИПИ · openfipi.devinf.ru
Похожие задания
24Текстовый файл состоит из заглавных букв латинского алфавита A, B, C, D, E и F. Определите максимальное…Подстрока и буквы: мин./макс. длина · 361E5224Текстовый файл состоит из заглавных букв латинского алфавита A, B, C, D, E и F. Определите в прилагаемом…Подстрока и буквы: мин./макс. длина · 88B22624Текстовый файл состоит из символов T, U, V, W, X, Y и Z. Определите в прилагаемом файле максимальное…Подстрока и буквы: мин./макс. длина · ACDF4D24Текстовый файл состоит из заглавных букв латинского алфавита A, B, C, D, E и F. Определите максимальное…Подстрока и буквы: мин./макс. длина · C2DB3924Текстовый файл состоит из десятичных цифр, знаков "+" и "*" (сложения и умножения). Определите максимальное…Корректное арифметическое выражение24Текстовый файл состоит из заглавных букв латинского алфавита А, В, С, D, Е и F. Определите в прилагаемом…Подстрока и буквы: мин./макс. длина
Нужен репетитор по информатике?
Посмотрите репетиторов, которые ведут занятия в Precettore, или оставьте заявку — подберём сами.
Готовьтесь к ЕГЭ по информатике в Precettore
Варианты с автопроверкой, домашние задания от репетитора, онлайн-доска и разбор ошибок — в одном кабинете. Регистрация бесплатная.