Задание EGEINFBDC5D0: Сортировка, отбор и моделирование

Решение.
Сначала нужно перевезти как можно больше контейнеров. Только среди загрузок с этим количеством выбираем наибольшую возможную массу самого тяжёлого контейнера.
Отсортируем массы по возрастанию и будем брать контейнеры начиная с самого лёгкого, пока следующий помещается. Пусть удалось взять k контейнеров. Для любого другого набора из k контейнеров его масса не меньше суммы k самых лёгких. Поэтому если первые k + 1 контейнеров уже превышают грузоподъёмность, никакой набор из k + 1 контейнеров не поместится.
Теперь максимизируем массу тяжелейшего контейнера, сохраняя количество k. Оставим первые k − 1 самых лёгких: их суммарная масса минимально возможная. Вместо последнего выбранного возьмём самый тяжёлый из остальных контейнеров, который помещается вместе с этой основой. Более тяжёлый контейнер не поместится даже с самой лёгкой основой, значит не поместится ни в каком допустимом наборе из k контейнеров.
Случай k = 0 обрабатываем отдельно: перевозимых контейнеров нет, оба выходных числа равны нулю. В исходном файле этот случай не возникает.
Программа на Python 3:

with open('26.txt') as f:
    capacity, n = map(int, f.readline().split())
    weights = sorted(int(f.readline()) for _ in range(n))

count = 0
total = 0
while count < n and total + weights[count] <= capacity:
    total += weights[count]
    count += 1

heaviest = 0
if count > 0:
    base = total - weights[count - 1]
    for weight in weights[count - 1:]:
        if base + weight <= capacity:
            heaviest = weight
print(count, heaviest)

Исходный файл содержит 9999 контейнеров, грузоподъёмность равна 99990. Получены следующие контрольные значения:

Поскольку 99932 ≤ 99990 < 99997, максимальное количество равно 1612. Для последнего контейнера остаётся 99990 − 99867 = 123 единицы грузоподъёмности. В файле максимальная масса контейнера равна 90, поэтому выбираем его; итоговая масса 99957 укладывается в ограничение.
Проверка. Независимый подсчёт количества контейнеров каждой массы и проверка каждого кандидата на самый тяжёлый дали тот же результат. Сортировка требует O(N log N) времени, дальнейшие проходы — O(N); память O(N).
Ответ: 1612 90.