Задание 27 ЕГЭ по информатике · 519CA0
Последовательности и подпоследовательностиВысокаяКЭС 3.2КЭС 3.16
Пусть S — последовательность из N целых чисел, пронумерованных подряд начиная с 1. Обозначим S(L,R) подпоследовательность, состоящую из идущих подряд элементов, входящих в S, начиная с элемента с номером L и заканчивая элементом с номером R. Требуется найти такие значения номеров элементов L, M, R, где 0<L<M<R−1 (то есть между элементами с номерами M и R есть ещё как минимум один элемент), чтобы разность суммы элементов подпоследовательности S(M+1,R) и суммы элементов подпоследовательности S(L,M) была максимальна. В ответе укажите максимальное значение разности подобных сумм.
Даны два входных файла — файл A и файл B. В первой строке каждого файла содержится число N (5≤N≤10 000 000) — количество целых чисел. Каждая из следующих N строк содержит одно целое число, значение которого по модулю не превышает 1000. Для файла B нельзя использовать переборный алгоритм, вычисляющий разность для всех возможных вариантов.
В ответе укажите два числа: сначала значение искомой величины для файла A, затем — для файла B.
1_519CA0.zipДаны два входных файла — файл A и файл B. В первой строке каждого файла содержится число N (5≤N≤10 000 000) — количество целых чисел. Каждая из следующих N строк содержит одно целое число, значение которого по модулю не превышает 1000. Для файла B нельзя использовать переборный алгоритм, вычисляющий разность для всех возможных вариантов.
В ответе укажите два числа: сначала значение искомой величины для файла A, затем — для файла B.
Показать ответ
120581; 133560104
Подсказки (3)
- Выразите обе суммы через префиксные суммы последовательности.
- Для фиксированного R нужно максимизировать PR−PM−(PM−PL), где Pi — сумма первых i элементов.
- Перебирайте R слева направо и храните минимум значения 2PM−PL для допустимых пар L<M<R−1. Текущая разность равна PR−(2PM−PL).
Решение
1. Обозначим через Pi сумму первых i элементов последовательности, причём P0=0. Тогда сумма элементов на отрезке [L;M] равна PM−PL−1, а сумма элементов на отрезке [M+1;R] равна PR−PM.
D=(PR−PM)−(PM−PL−1)=PR−2PM+PL−1
2. Для каждого правого конца R необходимо найти минимум величины 2PM−PL−1 среди всех допустимых пар L<M<R−1. При увеличении R в множество допустимых пар добавляется новая пара с M=R−2 и всеми допустимыми L<M.
DR=PR−min(2PM−PL−1)
3. Минимум можно поддерживать одной переменной. После обработки каждого элемента вычисляется очередное значение PR, обновляется ответ и добавляется в минимум подходящая пара. Алгоритм выполняется за O(N) времени и использует O(N) памяти при хранении префиксных сумм либо O(1) дополнительной памяти при потоковой обработке с необходимыми задержанными значениями.
4. Полученный алгоритм применяют отдельно к файлу A и к файлу B. Числовые ответы зависят от содержимого приложенных файлов.
D=(PR−PM)−(PM−PL−1)=PR−2PM+PL−1
2. Для каждого правого конца R необходимо найти минимум величины 2PM−PL−1 среди всех допустимых пар L<M<R−1. При увеличении R в множество допустимых пар добавляется новая пара с M=R−2 и всеми допустимыми L<M.
DR=PR−min(2PM−PL−1)
3. Минимум можно поддерживать одной переменной. После обработки каждого элемента вычисляется очередное значение PR, обновляется ответ и добавляется в минимум подходящая пара. Алгоритм выполняется за O(N) времени и использует O(N) памяти при хранении префиксных сумм либо O(1) дополнительной памяти при потоковой обработке с необходимыми задержанными значениями.
4. Полученный алгоритм применяют отдельно к файлу A и к файлу B. Числовые ответы зависят от содержимого приложенных файлов.
Частые ошибки
- Разрешают соседние отрезки, забывая условие $R>M+1$.
- Используют перебор всех троек $L$, $M$, $R$, что имеет кубическую или квадратичную сложность.
- Путают знак разности и вычисляют сумму левого отрезка минус сумму правого.
- Используют 32-битный тип данных без проверки диапазона сумм.
Источник: Открытый банк ФИПИ
Похожие задания
27Пусть S — последовательность из N целых чисел, пронумерованных подряд начиная с 1. Обозначим Si, Sj, Sk три…Последовательности и подпоследовательности · 3169CC27Пусть S — последовательность из N целых чисел, пронумерованных подряд начиная с 1. Обозначим Si, Sj, Sk три…Последовательности и подпоследовательности · 38414E27Пусть S — последовательность из N целых чисел, пронумерованных подряд начиная с 1. Обозначим S(L,R)…Последовательности и подпоследовательности · 952F4627Пусть S — последовательность из N целых чисел, пронумерованных подряд начиная с 1. Обозначим S(L,R)…Последовательности и подпоследовательности · A47CA127Пусть S — последовательность из N целых чисел, пронумерованных подряд начиная с 1. Обозначим Si, Sj, Sk три…Последовательности и подпоследовательности · A6A24727Пусть S — последовательность из N целых чисел, пронумерованных подряд начиная с 1. Обозначим S(L,R)…Последовательности и подпоследовательности · BDD715
Нужен репетитор по информатике?
Посмотрите репетиторов, которые ведут занятия в Precettore, или оставьте заявку — подберём сами.
Готовьтесь к ЕГЭ по информатике в Precettore
Варианты с автопроверкой, домашние задания от репетитора, онлайн-доска и разбор ошибок — в одном кабинете. Регистрация бесплатная.