images/home.png Начало
Имя: Пароль:
Зарегистрироваться
Восстановить пароль
18/04/2024 21:11:42

printРабочее место участника

Выбрать соревнование Задачи Послать решение Результаты проверки Статистика по задачам Вопросы и ответы Результаты соревнования Состояние сервера Изменить данные Управление командой Помощь

printЗадачи

1862. Переправа

Ограничения: время – 1s/2s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0) idea

Река Анк делит город на две половины: Анк и Морпорк. Каждое утро на левом берегу Анка скапливается очередь из желающих попасть на рынок, находящийся на правом берегу. Для переправы людей и товаров используется несколько типов лодок разной грузоподъемности. Количество лодок каждого типа не ограничено. Чтобы не гонять большие лодки впустую, необходимо минимизировать суммарный недогруз при переправе всех желающих и их грузов. Переправа должна выполняться в порядке очереди.
Напишите программу, которая определяет порядок подачи лодок для минимизации суммарного недогруза.
Формат ввода
Первая строка ввода содержит два целых числа - количество типов лодок `N` (`2\ ≤\ N\ ≤\ 50`) и количество грузов в очереди `M` (`1\ ≤\ M\ ≤\ 100\ 000`). Вторая строка ввода содержит `N` различных целых чисел в порядке возрастания в диапазоне от 50 до 1000 – грузоподъемность каждого типа лодок. Третья строка ввода содержит M целых чисел в диапазоне от 50 до 1000  – веса желающих переправиться вместе с их грузом. Существует по крайней мере один тип лодки, которая может перевести любой груз из очереди.
Формат вывода
Вывести в первой строке два целых числа – количество необходимых для переправы лодок `K` и минимальный суммарный недогруз `S`. Вторая строка должна содержать номера типов лодок в порядке их использования для перевозки. Если существует несколько вариантов, минимизирующих суммарный недогруз, то можно вывести любой из них.

Пример ввода

2 5
300 500
200 200 200 200 200

Пример вывода

3 300
1 2 2
loading