РУҚА
27

Ответ: Максимальная разность сумм

ЕГЭ · Информатика · Задание 27 · Динамическое программирование
ВысокаяФИПИBDD715Короткий ответ≈ 15 минут
Правильный ответ

Числовые ответы определить невозможно: файлы A и B в предоставленных материалах отсутствуют.

У этого задания официального ключа нет, поэтому ответ получен в разборе и с ключом не сверен. Перед тем как заучивать результат, пройдите выкладки — там видно, откуда взялось каждое число.

В бланк: число или слово без единиц измерения; дробную часть отделяйте запятой.

Условие

Пусть $S$ — последовательность из $N$ целых чисел, пронумерованных подряд начиная с 1. Обозначим $S(L, R)$ подпоследовательность, состоящую из идущих подряд элементов, входящих в $S$, начиная с элемента с номером $L$ и заканчивая элементом с номером $R$. Требуется найти такие значения номеров элементов $L$, $M$, $R$, где $0 < L < M < R - 1$, чтобы разность суммы элементов подпоследовательности $S(L, M)$ и суммы элементов подпоследовательности $S(M + 1, R)$ была максимальна. Даны два входных файла — файл A и файл B. В первой строке каждого файла содержится число $N$ ($5 \leq N \leq 10\,000\,000$), далее записаны $N$ целых чисел, каждое по модулю не превышает 1000. Для файла B нельзя использовать переборный алгоритм, вычисляющий разность для всех возможных вариантов.

Открыть задачу и решить самому

Где здесь ошибаются

Разрешают правой части состоять из одного элемента, хотя требуется $R > M + 1$.

Используют минимум префиксной суммы с недопустимым индексом.

Перебирают все тройки $L$, $M$, $R$, получая слишком высокую сложность.

Путают разность сумм с суммой модулей элементов.

Откуда взялся этот ответРазбор разложен на 4 шага: видно каждое преобразование и где теряется балл.
Открыть решение

Ответ к заданию 27 ЕГЭ, информатика

Официального ключа у этого задания нет, и ответ здесь получен в разборе. Поэтому рядом стоят выкладки: по ним видно, на чём ответ держится, и можно сверить свой ход решения, а не только результат.

Задача из темы «Динамическое программирование»: в ней 72 задачи — у каждой есть ответ и разбор по шагам. Регистрация не нужна.