Максимальная нечётная сумма

ЕГЭ · Информатика · Задание 27 · Динамическое программирование

ВысокаяФИПИA47CA1Короткий ответ≈ 10 минут

Пусть $S$ — последовательность из $N$ целых чисел, пронумерованных подряд начиная с 1. Обозначим $S(L, R)$ подпоследовательность, состоящую из идущих подряд элементов, входящих в $S$, начиная с элемента с номером $L$ и заканчивая элементом с номером $R$ включительно.

Требуется найти такую подпоследовательность $S(L, R)$ максимальной длины, что сумма её элементов отрицательна и нечётна. Гарантируется, что хотя бы одна подпоследовательность требуемого вида существует.

Дано два входных файла — файл A и файл B. В первой строке каждого файла содержится число $N$ ($5 \leq N \leq 10\,000\,000$) — количество целых чисел. Каждая из следующих $N$ строк содержит одно целое число, значение которого по модулю не превышает 1000. Найдите длину искомой подпоследовательности отдельно для файла A и файла B.

Файл к заданию

A47CA1.zipАрхив ZIP · 2,3 МБВнутри: 349_27_B.txt, 349_27_A.txt

Условие как в банке ФИПИ — открыть и сверить

Впишите правильный ответ.

Задание выполняется с использованием прилагаемых
файлов.

Пусть S – последовательность из N целых чисел, пронумерованных подряд начиная с 1. Обозначим S(L, R) подпоследовательность, состоящую из идущих подряд элементов, входящих в S, начиная с элемента с номером L и заканчивая элементом с номером R включительно.

Требуется найти такую подпоследовательность S(L, R) максимальной длины, что сумма её элементов отрицательна и нечётна. Гарантируется, что хотя бы одна подпоследовательность требуемого вида существует.

В ответе укажите длину искомой подпоследовательности.

Входные данные

Дано два входных файла (файл A и файл B), каждый из которых в первой строке содержит число N (5 ≤ N ≤ 10 000 000) – количество целых чисел. Каждая из следующих N строк содержит одно целое число, значение которого по модулю не превышает 1000. В ответе укажите два числа: сначала значение искомой величины для файла А, затем – для файла B.

Типовой пример организации данных во входном файле

–8

–5

При таких входных данных L = 2, R = 5. Сумма подпоследовательности равна (2 + (–8) + 4 + (–5)) = –7. Ответом является длина этой подпоследовательности, равная 4.

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.

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

Ваш ответ

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

3 уровня: от лёгкого толчка до почти готового решения. Следующий открывается, когда прочитан предыдущий, — чтобы не перепрыгнуть сразу к ответу.

1Мягкая — с чего смотретьуровень 1 из 3

Как представить сумму подпоследовательности через разности префиксных сумм?

2Наводящая — какие числа считатьуровень 2 из 3

Для каждого правого конца храните наиболее раннюю позицию префиксной суммы нужной чётности и подходящего знака.

3Прямая — фактически решениеуровень 3 из 3

Пусть $P_i$ — сумма первых $i$ элементов. Для подпоследовательности $(j+1, i)$ сумма равна $P_i-P_j$. Нужно максимизировать $i-j$ при $P_i-P_j<0$ и нечётной разности.

Всё равно не складывается?Полное решение с обоснованием каждого шага — на отдельной странице.

Открыть решение

ПредыдущаяМаксимальная чётная суммаСледующаяМаксимальная сумма разностей

Задание 27 ЕГЭ, информатика