Задача B. Вектор ≡

Условие

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

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

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

Входной файл содержит тройку чисел N A B, за которой следует N чисел P₁, P₂, …, P_N.

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

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

Ограничения

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

1 ≤ N ≤ 1000, 0 ≤ A, B, p_i ≤ 10⁶.

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

7 3 6
3 1 1 1 2 2 2

3
5 3 4

7 3 3
3 1 1 1 2 2 2

0

6 20 50
29 5 19 37 43 5

4
29 24 37 48

Разбор

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

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

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

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

T_R = max_L(T_L − 1 + 1).

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

1 ≤ L ≤ R,

A ≤ S_L,R ≤ B.

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

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