Задание 26: Обработка целочисленной информации

Сюжет обычно бытовой: архивация файлов, распределение ресурсов, обработка показаний датчиков. Во входном файле в первой строке даны параметры — например $S$ (ограничение) и $N$ (количество элементов, до 1000–5000), затем в $N$ строках идут сами числа $a_1, a_2, \dots, a_N$ (обычно натуральные, не больше 100). Нужно вывести одно или два числа-ответа: например, максимальное количество элементов, которые можно уместить в ограничение, и дополнительный параметр (максимальный или минимальный элемент в этом наборе). Задание оценивается в 2 балла — по одному баллу за каждое верно найденное число.

• $S$ — ограничение (объём диска, лимит времени, вместимость); $N$ — количество элементов; $a_1,\dots,a_N$ — значения.
• Префиксная сумма отсортированного по возрастанию массива: $P_k = a_{(1)}+a_{(2)}+\dots+a_{(k)}$.
• Монотонность: если массив отсортирован по возрастанию, $P_k$ не убывает при росте $k$, поэтому можно искать максимальное допустимое $k$ простым проходом или бинарным поиском.
• Условие допустимости набора из $k$ элементов: $P_k \le S$.
• Жадный принцип: чтобы вместить максимум элементов при ограничении суммы, берут наименьшие по значению элементы.
• Чтобы максимизировать «верхний» элемент в наборе при фиксированном $k$, используют метод последовательных замен наименьшего выбранного элемента на следующий по величине из оставшихся, если сумма остаётся $\le S$.
• Резерв после набора: $R = S - P_k$ — показывает, сколько «свободного места» остаётся для возможных замен.
• Суммарный объём данных редко превышает разумные пределы (например, $5000 \times 100 = 500000$), но тип переменной для суммы стоит выбирать с запасом.

1. Прочитать первую строку файла: значения $S$ и $N$.
2. Прочитать $N$ чисел в массив.
3. Отсортировать массив по возрастанию.
4. Накапливать сумму по возрастанию элементов, пока она не превысит $S$; число накопленных элементов — первый ответ $k$.
5. Зафиксировать сумму $P_k$ и текущий набор (первые $k$ элементов).
6. Для второго ответа применить метод замен: пытаться заменить наименьший элемент текущего набора на следующий недобранный элемент, если после замены сумма остаётся $\le S$; повторять, пока находятся выгодные замены.
7. Вывести два числа в требуемом порядке: количество элементов и найденный оптимальный параметр (например, максимальный размер файла).