Задание 27 ЕГЭ по информатике · A47CA1
Последовательности и подпоследовательностиВысокаяКЭС 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. Найдите длину искомой подпоследовательности отдельно для файла A и файла B.
1_A47CA1.zipТребуется найти такую подпоследовательность S(L,R) максимальной длины, что сумма её элементов отрицательна и нечётна. Гарантируется, что хотя бы одна подпоследовательность требуемого вида существует.
Дано два входных файла — файл A и файл B. В первой строке каждого файла содержится число N (5≤N≤10 000 000) — количество целых чисел. Каждая из следующих N строк содержит одно целое число, значение которого по модулю не превышает 1000. Найдите длину искомой подпоследовательности отдельно для файла A и файла B.
Показать ответ
5957; 1199892
Подсказки (3)
- Как представить сумму подпоследовательности через разности префиксных сумм?
- Для каждого правого конца храните наиболее раннюю позицию префиксной суммы нужной чётности и подходящего знака.
- Пусть Pi — сумма первых i элементов. Для подпоследовательности (j+1,i) сумма равна Pi−Pj. Нужно максимизировать i−j при Pi−Pj<0 и нечётной разности.
Решение
1. Введём префиксные суммы P0=0, Pi=a1+a2+⋯+ai. Сумма подпоследовательности от j+1 до i равна разности Pi−Pj.
S(j+1,i)=Pi−Pj
2. Разность Pi−Pj нечётна тогда и только тогда, когда префиксные суммы имеют разную чётность.
3. Условие отрицательности суммы имеет вид Pj>Pi. Для каждого текущего Pi нужно найти самый ранний индекс j среди префиксных сумм противоположной чётности, которые больше Pi.
4. Чтобы получить максимальную длину, достаточно хранить минимальный индекс для каждого возможного значения префиксной суммы и каждой чётности, а затем обрабатывать значения справа налево или использовать структуру данных для поиска минимального индекса среди сумм, больших текущей.
5. Алгоритм обрабатывает каждый элемент за логарифмическое время при использовании дерева отрезков или Fenwick tree после сжатия координат. Для каждого из файлов вычисляется отдельный максимум.
S(j+1,i)=Pi−Pj
2. Разность Pi−Pj нечётна тогда и только тогда, когда префиксные суммы имеют разную чётность.
3. Условие отрицательности суммы имеет вид Pj>Pi. Для каждого текущего Pi нужно найти самый ранний индекс j среди префиксных сумм противоположной чётности, которые больше Pi.
4. Чтобы получить максимальную длину, достаточно хранить минимальный индекс для каждого возможного значения префиксной суммы и каждой чётности, а затем обрабатывать значения справа налево или использовать структуру данных для поиска минимального индекса среди сумм, больших текущей.
5. Алгоритм обрабатывает каждый элемент за логарифмическое время при использовании дерева отрезков или Fenwick tree после сжатия координат. Для каждого из файлов вычисляется отдельный максимум.
Частые ошибки
- Проверяют только нечётность суммы и забывают условие отрицательности.
- Ищут подпоследовательность максимальной суммы вместо максимальной длины.
- Путают индекс префиксной суммы $j$ с левой границей подпоследовательности $j+1$.
Источник: Открытый банк ФИПИ
Похожие задания
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)…Последовательности и подпоследовательности · 952F4627Пусть S — последовательность из N целых чисел, пронумерованных подряд начиная с 1. Обозначим Si, Sj, Sk три…Последовательности и подпоследовательности · A6A24727Пусть S — последовательность из N целых чисел, пронумерованных подряд начиная с 1. Обозначим S(L,R)…Последовательности и подпоследовательности · BDD715
Нужен репетитор по информатике?
Посмотрите репетиторов, которые ведут занятия в Precettore, или оставьте заявку — подберём сами.
Готовьтесь к ЕГЭ по информатике в Precettore
Варианты с автопроверкой, домашние задания от репетитора, онлайн-доска и разбор ошибок — в одном кабинете. Регистрация бесплатная.