Задание 24 ЕГЭ по информатике · C00CCB
Другие формулировкиПовышеннаяКЭС 2.13КЭС 2.14
Задание выполняется с использованием прилагаемых файлов.
Текстовый файл состоит из символов T, U, V, W, X, Y и Z.
Определите в прилагаемом файле максимальное количество идущих подряд символов (длину непрерывной подпоследовательности), среди которых символ W встречается не более 130 раз.
Для выполнения этого задания следует написать программу.
308_24_C00CCB.txtТекстовый файл состоит из символов T, U, V, W, X, Y и Z.
Определите в прилагаемом файле максимальное количество идущих подряд символов (длину непрерывной подпоследовательности), среди которых символ W встречается не более 130 раз.
Для выполнения этого задания следует написать программу.
Показать ответ
237
Подсказки (3)
- Как организовать просмотр строки, чтобы одновременно хранить текущую подпоследовательность и количество символов W в ней?
- Используйте метод скользящего окна: расширяйте правую границу, а при количестве W больше 130 сдвигайте левую границу.
- Для каждой позиции правой границы уменьшайте окно слева, пока число символов W не станет не больше 130, и сохраняйте максимальную длину окна.
Решение
1. Задачу решаем одним проходом по строке с помощью двух границ окна. При добавлении очередного символа увеличиваем счётчик символов W, если добавлен именно W.
countW+=(s[r]=W)
2. Если в текущем окне оказалось более 130 символов W, сдвигаем левую границу вправо, уменьшая счётчик при удалении символа W.
countW>130⇒l+=1
3. После восстановления ограничения вычисляем длину текущего окна и сравниваем её с найденным максимумом.
length=r−l+1
4. При обработке приложенного файла максимальная длина допустимой непрерывной подпоследовательности равна 237.
max_length=237
countW+=(s[r]=W)
2. Если в текущем окне оказалось более 130 символов W, сдвигаем левую границу вправо, уменьшая счётчик при удалении символа W.
countW>130⇒l+=1
3. После восстановления ограничения вычисляем длину текущего окна и сравниваем её с найденным максимумом.
length=r−l+1
4. При обработке приложенного файла максимальная длина допустимой непрерывной подпоследовательности равна 237.
max_length=237
Частые ошибки
- Искать только самый длинный фрагмент с ровно 130 символами W, хотя допускается не более 130.
- Не сдвигать левую границу окна после превышения допустимого количества символов W.
- Пересчитывать каждый фрагмент заново и получать медленный алгоритм.
Источник: Открытый банк ФИПИ · openfipi.devinf.ru
Похожие задания
24Текстовый файл состоит из символов T, U, V, W, X, Y и Z. Определите в прилагаемом файле максимальное…Другие формулировки · 7E659E24Текстовый файл состоит из десятичных цифр и заглавных букв латинского алфавита. Определите в этом файле…Другие формулировки · 931D9C24Текстовый файл состоит из символов, обозначающих прописные буквы латинского алфавита. Определите максимальное…Другие формулировки · A9D03C24Текстовый файл состоит из символов, обозначающих прописные буквы латинского алфавита. Определите максимальное…Другие формулировки · BAC4D124Текстовый файл состоит из символов T, U, V, W, X, Y и Z. Определите в прилагаемом файле минимальное…Другие формулировки · DD0C3824Текстовый файл состоит из заглавных букв латинского алфавита Q, R, W и цифр 1, 2, 4. Определите в прилагаемом…Другие формулировки · E7442424Текстовый файл состоит из символов T, U, V, W, X, Y и Z. Определите в прилагаемом файле минимальное…Другие формулировки · F04010
Нужен репетитор по информатике?
Посмотрите репетиторов, которые ведут занятия в Precettore, или оставьте заявку — подберём сами.
Готовьтесь к ЕГЭ по информатике в Precettore
Варианты с автопроверкой, домашние задания от репетитора, онлайн-доска и разбор ошибок — в одном кабинете. Регистрация бесплатная.