Задание 24 ЕГЭ по информатике · 199381
Подстрока и буквы: мин./макс. длинаВысокаяКЭС 3.9
Задание выполняется с использованием прилагаемых файлов.
Текстовый файл состоит из заглавных букв латинского алфавита A, B, C, D, E и F.
Определите минимальное количество идущих подряд символов в прилагаемом файле, среди которых пара символов AB (в указанном порядке) встречается ровно 220 раз.
Для выполнения этого задания следует написать программу.
325_24_199381.txtТекстовый файл состоит из заглавных букв латинского алфавита A, B, C, D, E и F.
Определите минимальное количество идущих подряд символов в прилагаемом файле, среди которых пара символов AB (в указанном порядке) встречается ровно 220 раз.
Для выполнения этого задания следует написать программу.
Показать ответ
1088
Подсказки (3)
- Как можно быстро посчитать количество вхождений пары AB в каждом рассматриваемом фрагменте?
- Рассматривайте файл как строку и используйте префиксные суммы: для каждой позиции подсчитайте, начинается ли там пара AB.
- Для каждой левой границы найдите минимальную правую границу, на которой число пар AB становится равным 220. Выберите наименьшую длину полученного фрагмента.
Решение
1. Сначала считываем строку из файла и для каждой позиции i проверяем условие: символ в позиции i равен A, а следующий символ равен B. 2. Строим префиксные суммы количества вхождений AB. Тогда число таких пар на отрезке с границами l и r вычисляется за постоянное время. 3. Перебираем левую границу фрагмента и с помощью двух указателей либо бинарного поиска находим минимальную правую границу, при которой внутри фрагмента ровно 220 вхождений AB. 4. Среди всех подходящих фрагментов выбираем минимальную длину и выводим её.
Частые ошибки
- Считать перекрывающиеся вхождения неправильно.
- Искать только неперекрывающиеся подстроки.
- Не учитывать, что пара AB может начинаться на последнем символе выбранного фрагмента и выходить за его границу.
- Минимизировать число пар вместо длины фрагмента.
Источник: Открытый банк ФИПИ · openfipi.devinf.ru
Похожие задания
24Задание выполняется с использованием прилагаемых к заданию файлов. Текстовый файл состоит не более чем из 1…Подстрока и буквы: мин./макс. длина · A520F824Задание выполняется с использованием прилагаемых к заданию файлов. Текстовый файл состоит не более чем из 1…Подстрока и буквы: мин./макс. длина · AA7E8A24Задание выполняется с использованием прилагаемых к заданию файлов. Текстовый файл состоит не более чем из 1…Подстрока и буквы: мин./макс. длина · B31CB524Задание выполняется с использованием прилагаемых к заданию файлов. Текстовый файл состоит не более чем из 1…Подстрока и буквы: мин./макс. длина · B92F0024Текстовый файл состоит из заглавных букв латинского алфавита A, B, C, D, E и F. Определите максимальное…Подстрока и буквы: мин./макс. длина · 2AB91624Текстовый файл состоит из заглавных букв латинского алфавита A, B, C, D, E и F. Определите в прилагаемом…Подстрока и буквы: мин./макс. длина · 3380E024Текстовый файл состоит из заглавных букв латинского алфавита A, B, C, D, E и F. Определите максимальное…Подстрока и буквы: мин./макс. длина · 361E5224Текстовый файл состоит из заглавных букв латинского алфавита A, B, C, D, E и F. Определите в прилагаемом…Подстрока и буквы: мин./макс. длина · 88B226
Нужен репетитор по информатике?
Посмотрите репетиторов, которые ведут занятия в Precettore, или оставьте заявку — подберём сами.
Готовьтесь к ЕГЭ по информатике в Precettore
Варианты с автопроверкой, домашние задания от репетитора, онлайн-доска и разбор ошибок — в одном кабинете. Регистрация бесплатная.