ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

Чемпионат Урала 2012

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

B. Космический лифт

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Уже много лет космические корабли взлетают не с поверхности Земли, а из огромного порта, расположенного на геостационарной орбите и соединённого с Землёй тросами из углеродных нанотрубок. По тросам ходят лифты, доставляющие людей и грузы на орбиту.
Завтра группа ключевых сотрудников корпорации «Акросс» отправится в космопорт с секретным идеологическим заданием. Руководство космопорта выделило для доставки людей на орбиту специальный двухместный лифт. Глава «Акросса» потребовал, чтобы в любой момент времени суммарная значимость сотрудников, находящихся в лифте, не превышала некоторой фиксированной величины. При этом условии даже в случае чрезвычайного происшествия потеря корпорации не будет невосполнимой. Сотрудники садятся в лифт в порядке живой очереди. Лифт отправляют наверх, если в него зашли уже два человека, либо же зашёл один человек, но следующий за ним слишком значим для корпорации, чтобы их вместе можно было отправить в одном лифте.
Руководство космопорта хочет узнать максимальное количество рейсов, которое может потребоваться для перевозки всех сотрудников, чтобы заранее запасти необходимое количество кислородных баллонов и заряженных аккумуляторов.

Исходные данные

В первой строке записаны целые числа n и s — количество сотрудников «Акросса», отправляющихся на задание, и максимальная суммарная значимость двух сотрудников, при которой они могут вместе ехать в лифте (1 ≤ n ≤ 105; 1 ≤ s ≤ 109). Во второй строке записаны целые числа v1, …, vn — значимости сотрудников (1 ≤ vis).

Результат

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

Пример

исходные данныерезультат
6 6
1 2 3 3 4 5
5
2 5 1 3 4 3
Автор задачи: Алексей Самсонов
Источник задачи: XVI Открытый чемпионат Урала по спортивному программированию (апрель, 2012)
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1901. Космический лифт