Задание 27 ЕГЭ по информатике · 952F46
Последовательности и подпоследовательностиВысокаяКЭС 3.2КЭС 3.16
Пусть S — последовательность из N целых чисел, пронумерованных подряд начиная с 1. Обозначим S(L,R) подпоследовательность, состоящую из идущих подряд элементов, входящих в S, начиная с элемента с номером L и заканчивая элементом с номером R включительно. Требуется найти подпоследовательность S(L,R) максимальной длины, сумма элементов которой положительна и чётна. Гарантируется, что хотя бы одна такая подпоследовательность существует.
Даны два входных файла, файл A и файл B. В первой строке каждого файла содержится число N (5≤N≤10 000 000), затем следуют N целых чисел, каждое по модулю не превышает 1000. Для каждого файла определите длину искомой подпоследовательности. Типовой пример из условия является иллюстративным; используйте данные из приложенных файлов.
1_952F46.zipДаны два входных файла, файл A и файл B. В первой строке каждого файла содержится число N (5≤N≤10 000 000), затем следуют N целых чисел, каждое по модулю не превышает 1000. Для каждого файла определите длину искомой подпоследовательности. Типовой пример из условия является иллюстративным; используйте данные из приложенных файлов.
Показать ответ
5984; 1201278
Подсказки (3)
- Рассмотрите суммы на префиксах последовательности и их чётность.
- Для каждого правого конца подпоследовательности достаточно знать минимальную префиксную сумму подходящей чётности.
- Поддерживайте первые позиции префиксов с чётной и нечётной суммой, а также минимальные значения таких сумм. Проверяйте, чтобы разность сумм была положительной и чётной.
Решение
1. Обозначим префиксную сумму через Pi=a1+a2+⋯+ai, причём P0=0. Сумма подпоследовательности S(L,R) равна PR−PL−1.
2. Сумма PR−PL−1 чётна тогда и только тогда, когда PR и PL−1 имеют одинаковую чётность.
3. Для каждого текущего R выбираем среди ранее встречавшихся префиксов той же чётности такой, у которого минимальная сумма. Это обеспечивает положительную разность и максимальную длину при подходящем индексе.
4. Алгоритм обрабатывает каждый элемент один раз, хранит минимальные префиксные суммы и соответствующие позиции для двух чётностей. Его сложность — O(N) по времени и O(1) по дополнительной памяти.
2. Сумма PR−PL−1 чётна тогда и только тогда, когда PR и PL−1 имеют одинаковую чётность.
3. Для каждого текущего R выбираем среди ранее встречавшихся префиксов той же чётности такой, у которого минимальная сумма. Это обеспечивает положительную разность и максимальную длину при подходящем индексе.
4. Алгоритм обрабатывает каждый элемент один раз, хранит минимальные префиксные суммы и соответствующие позиции для двух чётностей. Его сложность — O(N) по времени и O(1) по дополнительной памяти.
Частые ошибки
- Перебирать все пары границ подпоследовательности.
- Проверять только чётность суммы, не проверяя её положительность.
- Забывать префикс $P_0=0$.
- Использовать тип данных, недостаточный для хранения суммы при больших $N$.
Источник: Открытый банк ФИПИ
Похожие задания
27Пусть S — последовательность из N целых чисел, пронумерованных подряд начиная с 1. Обозначим Si, Sj, Sk три…Последовательности и подпоследовательности · 3169CC27Пусть S — последовательность из N целых чисел, пронумерованных подряд начиная с 1. Обозначим Si, Sj, Sk три…Последовательности и подпоследовательности · 38414E27Пусть S — последовательность из N целых чисел, пронумерованных подряд начиная с 1. Обозначим S(L,R)…Последовательности и подпоследовательности · 519CA027Пусть S — последовательность из N целых чисел, пронумерованных подряд начиная с 1. Обозначим S(L,R)…Последовательности и подпоследовательности · A47CA127Пусть S — последовательность из N целых чисел, пронумерованных подряд начиная с 1. Обозначим Si, Sj, Sk три…Последовательности и подпоследовательности · A6A24727Пусть S — последовательность из N целых чисел, пронумерованных подряд начиная с 1. Обозначим S(L,R)…Последовательности и подпоследовательности · BDD715
Нужен репетитор по информатике?
Посмотрите репетиторов, которые ведут занятия в Precettore, или оставьте заявку — подберём сами.
Готовьтесь к ЕГЭ по информатике в Precettore
Варианты с автопроверкой, домашние задания от репетитора, онлайн-доска и разбор ошибок — в одном кабинете. Регистрация бесплатная.