Задание 24 ЕГЭ по информатике · DD0C38
Другие формулировкиПовышеннаяКЭС 2.13КЭС 2.14
Задание выполняется с использованием прилагаемых файлов.
Текстовый файл состоит из символов T, U, V, W, X, Y и Z.
Определите в прилагаемом файле минимальное количество идущих подряд символов (длину непрерывной подпоследовательности), среди которых символ W встречается не менее 240 раз.
Для выполнения этого задания следует написать программу.
325_24_DD0C38.txtТекстовый файл состоит из символов T, U, V, W, X, Y и Z.
Определите в прилагаемом файле минимальное количество идущих подряд символов (длину непрерывной подпоследовательности), среди которых символ W встречается не менее 240 раз.
Для выполнения этого задания следует написать программу.
Показать ответ
624
Подсказки (3)
- Рассмотрите отрезок строки с двумя границами и поддерживайте количество символов W внутри него.
- Используйте метод скользящего окна: расширяйте правую границу, а затем сдвигайте левую, пока в окне остаётся не менее 240 символов W.
- Для каждого правого конца вычисляйте минимальную длину подходящего окна: right−left+1.
Решение
1. Считываем строку из файла и рассматриваем её как последовательность символов.
2. Двигаем правую границу окна слева направо. При встрече символа W увеличиваем счётчик символов W.
countW+=1
3. Когда в окне становится не менее 240 символов W, сдвигаем левую границу вправо, пока условие сохраняется. На каждом шаге обновляем минимальную длину окна.
L=right−left+1
4. Каждый символ добавляется в окно и удаляется из него не более одного раза, поэтому алгоритм работает за линейное время.
O(n)
2. Двигаем правую границу окна слева направо. При встрече символа W увеличиваем счётчик символов W.
countW+=1
3. Когда в окне становится не менее 240 символов W, сдвигаем левую границу вправо, пока условие сохраняется. На каждом шаге обновляем минимальную длину окна.
L=right−left+1
4. Каждый символ добавляется в окно и удаляется из него не более одного раза, поэтому алгоритм работает за линейное время.
O(n)
Частые ошибки
- Перебирать все пары границ и получить квадратичную сложность.
- Не уменьшать счётчик при удалении символа W из левой части окна.
- Искать только первый подходящий фрагмент, не проверяя возможность его дальнейшего сокращения.
Источник: Открытый банк ФИПИ · openfipi.devinf.ru
Похожие задания
24Текстовый файл состоит из десятичных цифр и заглавных букв латинского алфавита. Определите в этом файле…Другие формулировки · 931D9C24Текстовый файл состоит из символов, обозначающих прописные буквы латинского алфавита. Определите максимальное…Другие формулировки · A9D03C24Текстовый файл состоит из символов, обозначающих прописные буквы латинского алфавита. Определите максимальное…Другие формулировки · BAC4D124Текстовый файл состоит из символов T, U, V, W, X, Y и Z. Определите в прилагаемом файле максимальное…Другие формулировки · C00CCB24Текстовый файл состоит из заглавных букв латинского алфавита Q, R, W и цифр 1, 2, 4. Определите в прилагаемом…Другие формулировки · E7442424Текстовый файл состоит из символов T, U, V, W, X, Y и Z. Определите в прилагаемом файле минимальное…Другие формулировки · F04010
Нужен репетитор по информатике?
Посмотрите репетиторов, которые ведут занятия в Precettore, или оставьте заявку — подберём сами.
Готовьтесь к ЕГЭ по информатике в Precettore
Варианты с автопроверкой, домашние задания от репетитора, онлайн-доска и разбор ошибок — в одном кабинете. Регистрация бесплатная.