Задание 27 ЕГЭ по информатике · 38414E
Последовательности и подпоследовательностиВысокаяКЭС 3.2КЭС 3.16
Пусть S — последовательность из N целых чисел, пронумерованных подряд начиная с 1. Обозначим Si, Sj, Sk три элемента последовательности S, где i<j<k. Определите в последовательности S три таких числа Si, Sj, Sk, что Si>Sj, Sk>Sj, и значение выражения (Si−Sj)+(Sk−Sj) максимально. В ответе укажите найденное максимальное значение выражения. Гарантируется, что в последовательности есть три числа, удовлетворяющие условию задачи.
Дано два входных файла — файл А и файл B. Каждый из них в первой строке содержит число N (5≤N≤10 000 000) — количество целых чисел. Каждая из следующих N строк содержит одно целое число, значение которого по модулю не превышает 1000. Для файла B необходимо использовать алгоритм, не перебирающий все возможные тройки элементов.
1_38414E.zipДано два входных файла — файл А и файл B. Каждый из них в первой строке содержит число N (5≤N≤10 000 000) — количество целых чисел. Каждая из следующих N строк содержит одно целое число, значение которого по модулю не превышает 1000. Для файла B необходимо использовать алгоритм, не перебирающий все возможные тройки элементов.
Показать ответ
935; 1293
Подсказки (3)
- Как можно представить выражение (Si−Sj)+(Sk−Sj) через сумму двух величин, зависящих от разных частей последовательности?
- Для каждого среднего элемента Sj нужно знать максимальный элемент слева и максимальный элемент справа: значение равно maxi<jSi+maxk>jSk−2Sj.
- Просматривайте последовательность слева направо, поддерживая максимум слева, а максимумы справа заранее вычислите суффиксным проходом. Для каждого j обновляйте общий максимум.
Решение
1. Преобразуем выражение:
(Si−Sj)+(Sk−Sj)=Si+Sk−2Sj
2. При фиксированном среднем индексе j выгодно выбрать максимальный элемент слева от него и максимальный элемент справа от него.
Fj=maxi<jSi+maxk>jSk−2Sj
3. Сначала построим массив суффиксных максимумов: Rj=max(Sj,Sj+1,…,SN). Затем одним проходом слева направо будем хранить максимум элементов с индексами меньше j и вычислять Fj.
4. Максимальное из всех значений Fj является ответом. Алгоритм работает за O(N) времени и использует O(N) памяти либо O(1) дополнительной памяти при обработке справа налево с подходящими переменными.
(Si−Sj)+(Sk−Sj)=Si+Sk−2Sj
2. При фиксированном среднем индексе j выгодно выбрать максимальный элемент слева от него и максимальный элемент справа от него.
Fj=maxi<jSi+maxk>jSk−2Sj
3. Сначала построим массив суффиксных максимумов: Rj=max(Sj,Sj+1,…,SN). Затем одним проходом слева направо будем хранить максимум элементов с индексами меньше j и вычислять Fj.
4. Максимальное из всех значений Fj является ответом. Алгоритм работает за O(N) времени и использует O(N) памяти либо O(1) дополнительной памяти при обработке справа налево с подходящими переменными.
Частые ошибки
- Перебирать все тройки индексов, получая сложность $O(N^3)$.
- Не учитывать порядок индексов $i<j<k$.
- Использовать минимум слева или справа вместо максимума.
- Вычитать $S_j$ только один раз вместо двух.
Источник: Открытый банк ФИПИ
Похожие задания
27Пусть S — последовательность из N целых чисел, пронумерованных подряд начиная с 1. Обозначим Si, Sj, Sk три…Последовательности и подпоследовательности · 3169CC27Пусть S — последовательность из N целых чисел, пронумерованных подряд начиная с 1. Обозначим S(L,R)…Последовательности и подпоследовательности · 519CA027Пусть 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
Варианты с автопроверкой, домашние задания от репетитора, онлайн-доска и разбор ошибок — в одном кабинете. Регистрация бесплатная.