Олимпиадный тренинг

Задача . 3154


Задача

Темы:
Для перевозки партии грузов различной массы выделен грузовик, но его грузоподъёмность ограничена, поэтому перевезти сразу все грузы не удастся. Грузы массой от 310 до 320 кг включительно грузят в первую очередь, выбирая грузы по убыванию массы, начиная с самого тяжёлого. На оставшееся после этого место стараются взять как можно большее количество грузов. Если это можно сделать несколькими способами, выбирают тот способ, при котором самый большой из выбранных грузов имеет наибольшую массу. Если и при этом условии возможно несколько вариантов, выбирается тот, при котором наибольшую массу имеет второй по величине груз, и т.д. Известны количество грузов, масса каждого из них и грузоподъёмность грузовика. Необходимо определить количество и общую массу грузов, которые будут вывезены при погрузке по вышеописанным правилам.
Входные данные. Первая строка входного файла 26-39.txt записаны два числа: два целых числа: N – общее количество грузов и M – грузоподъёмность грузовика в кг. Каждая из следующих N строк содержит одно целое число – массу груза в кг. В ответе запишите два целых числа: сначала максимально возможное количество грузов, затем их общую массу.
Пример входного файла:
6 720
100
315
120
160
140
300
В данном случае сначала нужно взять груз массой 315 кг. Остается 405 кг. После этого можно вывезти ещё максимум 3 груза. Это можно сделать тремя способами: 100 + 120 + 140, 100 + 140 + 160, 100 + 120 + 160. Выбираем способ, при котором вывозится груз наибольшей возможной массы. Таких способов два: 100 + 120 + 160, 100 + 140 + 160. Из этих способов выбираем тот, при котором больше масса второго по величине груза, то есть 100 + 140 + 160. Всего получается 4 груза общей массой 715 кг. Ответ: 4 715.

time 1000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
Комментарий учителя