Системный администратор раз в неделю создаёт архив пользовательских файлов. Однако объём диска, куда он помещает архив, может быть меньше, чем суммарный объём архивируемых файлов.
Известно, какой объём занимает файл каждого пользователя. По заданной информации об объёме файлов пользователей и свободном объёме на архивном диске определите максимальное число пользователей, чьи файлы можно сохранить в архиве, а также максимальный размер имеющегося файла, который может быть сохранён в архиве, при условии, что сохранены файлы максимально возможного числа пользователей.
Входные данные.
В первой строке входного файла находятся два числа: S — размер свободного места на диске (натуральное число, не превышающее 10 000) и N — количество пользователей (натуральное число, не превышающее 1000). В следующих N строках находятся значения объёмов файлов каждого пользователя (все числа натуральные, не превышающие 100), каждое — в отдельной строке.
Запишите в ответе два числа через пробел: сначала наибольшее число пользователей, чьи файлы могут быть помещены в архив, затем — максимальный размер имеющегося файла, который может быть сохранён в архиве, при условии, что сохранены файлы максимально возможного числа пользователей.
Размер свободного места на диске — 8200
1. Сначала переносим столбец с объемами памяти из текстового файла в Exel, а затем сортируем столбец А по возрастанию:
2. Далее, начиная с ячейки А1, начинаем спускать вниз, выделяя диапазон. В это время смотрим как меняется счетчик суммы в правом нижнем углу:
3. Получается, что 568 пользователей с самыми маленькими объемами памяти занимают 8176 места. Больше взять не можем, так как у нас ограничение в 8200
4. Теперь нужно найти размер максимального файла. 567 пользователей занимают 8147 (минус ячейка А568) памяти, тогда получается, что на еще одного пользователя может приходиться 53 свободного места. Проверяем, есть ли такой объем памяти в файле — нет, такого нет. Тогда ищем следующее максимальное число меньшее 53, это 50. Значит максимальный объем памяти — 50.
Таким образом, ответ — 568 50