Перевозка контейнеров
На грузовом судне необходимо перевезти контейнеры, имеющие одинаковый габарит и разные массы. Общая масса всех контейнеров превышает грузоподъёмность судна. Количество грузовых мест на судне не меньше количества контейнеров, назначенных к перевозке. Какое максимальное количество контейнеров можно перевезти за один рейс и какова масса самого тяжёлого контейнера среди всех контейнеров, которые можно перевезти за один рейс?
В первой строке входного файла находятся два числа: $S$ — грузоподъёмность судна, натуральное число, не превышающее 100 000, и $N$ — количество контейнеров, натуральное число, не превышающее 10 000. В следующих $N$ строках находятся значения масс контейнеров, требующих транспортировки. Все числа натуральные, не превышающие 100, каждое указано в отдельной строке.
Два целых неотрицательных числа: максимальное количество контейнеров, которые можно перевезти за один рейс, и масса наиболее тяжёлого из них.
Условие как в банке ФИПИ — открыть и сверить
|
На грузовом судне необходимо перевезти контейнеры, имеющие одинаковый габарит и разные массы. Общая масса всех контейнеров превышает грузоподъёмность судна. Количество грузовых мест на судне не меньше количества контейнеров, назначенных к перевозке. Какое максимальное количество контейнеров можно перевезти за один рейс и какова масса самого тяжёлого контейнера среди всех контейнеров, которые можно перевезти за один рейс?
Входные данные. В первой строке входного файла находятся два числа: S грузоподъёмность судна (натуральное число, не превышающее 100 000) и N количество контейнеров (натуральное число, не превышающее 10 000). В следующих N строках находятся значения масс контейнеров, требующих транспортировки (все числа натуральные, не превышающие 100), каждое в отдельной строке.
Выходные данные. Два целых неотрицательных числа: максимальное количество контейнеров, которые можно перевезти за один рейс и масса наиболее тяжёлого из них. Пример входного файла: 100 4 80 30 50 40
При таких исходных данных можно транспортировать за один раз максимум 2 контейнера. Возможные массы этих двух контейнеров 30 и 40, 30 и 50 или 40 и 50. Поэтому ответ для приведённого примера:
| |||||||
| |
Формат: число или слово без единиц измерения; дробную часть отделяйте запятой.
1Мягкая — с чего смотретьуровень 1 из 3
Какие контейнеры выгоднее всего выбрать, чтобы перевезти их максимальное количество?
2Наводящая — какие числа считатьуровень 2 из 3
Отсортируйте массы по возрастанию и последовательно добавляйте самые лёгкие контейнеры, пока их суммарная масса не превысит $S$.
3Прямая — фактически решениеуровень 3 из 3
Если после выбора контейнеров их количество равно $k$, то первый ответ — $k$, а второй ответ — максимальная масса среди выбранных контейнеров, то есть масса $k$-го элемента отсортированного массива.