Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
995. Вектор
Динамическое программирование и запоминающие функцииОлимпиадные задачи на русском языке
| 03/07/2008 | Лето 2008 дорешивание ( 7J) |
| 16/07/2008 | Лето 2008 - 7 (J) |
Ограничения: время – 2s/4s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Дан целочисленный вектор `p_1,\ p_2,\ …,\ p_N`. Над любым вектором,
состоящим из двух и более элементов, определим операцию сжатия,
состоящую в замене произвольной пары соседних элементов на их сумму.
Например, вектор `1\ 2\ 3` в результате сжатия может превратиться в
вектор `3\ 3` либо `1\ 5`.
Требуется путем последовательного применения операции сжатия получить из
исходного вектора вектор максимально возможной длины, все элементы которого
не меньше `A` и не больше `B`.
Ввод
Входной файл содержит тройку чисел `N\ A\ B`, за которой следует `N` чисел `p_i`.
Все числа во входном файле целые.
`1\ ≤\ N\ ≤\ 1000`, `0\ ≤\ A,\ B,\ p_i\ ≤\ 10^6`.
Вывод
Выходной файл должен содержать длину результирующего вектора, за которой
следуют его элементы.
Если решений не существует, вывести единственное число `0`.
Если решений несколько, вывести любое из них.
Пример ввода 1
7 3 6 3 1 1 1 2 2 2
Пример вывода 1
3 5 3 4
Пример ввода 2
7 3 3 3 1 1 1 2 2 2
Пример вывода 2
0
Пример ввода 3
6 20 50 29 5 19 37 43 5
Пример вывода 3
4 29 24 37 48
