Задание 26. Информатика. ЕГЭ. Шастин. 7.6.2025

(Д. Бахтиев) Во время погрузки корабля все грузы последовательно подаются к причалу. Каждый груз имеет массу (в килограммах) — целое положительное число.

Для равномерной загрузки и обеспечения безопасности все грузы нужно распределить по трюмам корабля по следующим правилам: в один трюм можно поместить любое количество грузов, но при этом разница между самым лёгким и самым тяжёлым грузом в трюме не должна превышать \(T\) кг, а общая масса грузов в трюме не должна превышать \(M\) кг. Также известно, что грузы помещаются в трюмы в порядке неубывания их масс. Если груз по массе не может быть добавлен ни в один из уже созданных трюмов, для него открывается новый трюм

Входные данные:

В первой строке заданы три целых числа \(N\) — количество грузов \((1 \leqslant N \leqslant 100000),\) \(T\) — максимальная разница между массами грузов одного трюма \((1 \leqslant T \leqslant 1000),\) \(M\) — максимальная общая масса грузов одного трюма \((1 \leqslant M \leqslant 10^9).\) Каждая из следующих \(N\) строк содержит одно целое число — массу груза в килограммах (от \(1\) до \(10^6),\) в произвольном порядке.

Запишите в ответе два числа: сначала минимально возможное общее количество трюмов, использованных для размещения всех грузов, затем при таком размещении определите максимально возможное количество грузов, размещённых в том же трюме, что и самый маленький по массе груз.

Типовой пример организации данных во входном файле

\(8 \,\, 50 \,\, 300\)
\(30\)
\(20\)
\(70\)
\(10\)
\(250\)
\(200\)
\(150\)
\(80\)

При таких исходных данных в первый трюм можно поместить грузы, с массами: \(30,\) \(20\) и \(10,\) во второй \(70\) и \(80,\) в третий, четвёртый и пятый будут складированы по одному грузу — \(150,\) \(200\) и \(250\) (из-за общего ограничения по массе в одном трюме). Ответ: \(5 \,\, 3.\)

fp = open('26_22606.txt')
N, T, M = map(int, fp.readline().split())
cargo = [int(x) for x in fp]
cargo.sort()
holds = [[cargo.pop(0)]]

while cargo:
    g = cargo.pop(0)
    f = False
    for i in range(len(holds)):
        if sum(holds[i]) + g < M and g - holds[i][0] <= T:
            holds[i].append(g)
            f = True
            break
    if not f:
        holds.append([g])
print(len(holds), len(holds[0]))