Задача D. Вектор

Автор:И. Бураго   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

Дан целочисленный вектор P1, P2, …, PN. Над любым вектором, состоящим из двух и более элементов, определим операцию сжатия, состоящую в замене произвольной пары соседних элементов на их сумму. Например, вектор 123 в результате сжатия может превратиться в вектор 33 либо 15.

Требуется путем последовательного применения операции сжатия получить из исходного вектора вектор максимально возможной длины, все элементы которого не меньше A и не больше B.

Формат входного файла

Входной файл содержит тройку чисел N A B, за которой следует N чисел P1, P2, …, PN.

Формат выходного файла

Выходной файл должен содержать длину результирующего вектора, за которой следуют его элементы. Если решений не существует, вывести единственное число 0. Если решений несколько, вывести любое из них.

Ограничения

Все числа во входном файле целые.

1 ≤ N ≤ 1000, 0 ≤ A, B, pi ≤ 106.

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
7 3 6
3 1 1 1 2 2 2
3
5 3 4
2
7 3 3
3 1 1 1 2 2 2
0
3
6 20 50
29 5 19 37 43 5
4
29 24 37 48

Разбор

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

Фиксируем некоторое R (1 ≤ R ≤ N) и рассмотрим участок исходного вектора с 1-го по R-й элемент включительно. Обозначим за TR длину наилучшего решения на этом отрезке, а за SL,R — сумму элементов вектора с L-го по R-й. Ясно, что TR определяется как разность R и количества операций сжатия, произведенных на рассматриваемом интервале.

Крайнее на текущем фрагменте R-е число может быть просуммировано с 0, 1, …, R − 1 элементами, стоящими слева от него. Оставим в рассмотрении только те из этих вариантов, при которых получающаяся сумма SL,R находится в диапазоне от A до B. В таком случае для каждого L (1 ≤ L ≤ R) возможно выразить решение на рассматриваемом интервале через наилучшее сжатие фрагмента вектора с 1-го по (L − 1)-й элементы. Действительно, при условии, что элементы с L-го по R-й будут заменены единственным числом, наилучшее решение определяется сжатием первых L − 1 элементов вектора.

Таким образом, рассматриваются все возможные для R-го элемента варианты, т. е.

TR = maxL(TL − 1 + 1).

Здесь при вычислении максимума необходимо перебрать все L, для которых существует решение на фрагменте c 1-го по (L − 1)-й элементы и одновременно выполнены условия:

1 ≤ L ≤ R,

A ≤ SL,R ≤ B.

Последовательное рассмотрение всех возможных значений R дает в конечном итоге ответ — длину TN искомого вектора.

По условию задачи также требуется установить не только длину оптимального решения, но и сам результат сжатия. Результирующий вектор состоит из TN элементов. Его вычисление удобно начинать с конца. Для этого необходимо для каждого R помимо TR запомнить еще и значение LR, при котором достигается максимум. Тогда последний элемент будет равен сумме элементов исходного вектора с LN-го по N-й, предпоследний — сумме элементов с LLN − 1-го по LN − 1-й, и т. д.


0.163s 0.013s 13