Задача с сайта https://kpolyakov.spb.ru/
На складе требуется разместить контейнеров различного размера, каждый из которых имеет форму куба. Чтобы сэкономить место, контейнеры вкладывают друг в друга. Один контейнер можно вложить в другой, если размер стороны внешнего контейнера превышает размер стороны внутреннего на
и более условных единиц. Группу вложенных друг в друга контейнеров называют блоком. Количество контейнеров в блоке может быть любым. Каждый блок, независимо от количества и размера входящих в него контейнеров, а также каждый одиночный контейнер, не входящий в блоки, занимает при хранении одну складскую ячейку. Определите минимальное количество ячеек, которые потребуются для хранения всех контейнеров, и максимальное количество контейнеров в одном блоке.
Входные данные представлены в файле 26-101.txt следующим образом. В первой строке входного файла записано число – количество контейнеров (натуральное число, не превышающее 20 000) и число
(
) – наименьшая допустимая разница размеров вложенных соседних контейнеров. Каждая из следующих
строк содержит одно натуральное число, не превышающее 10000 – длину стороны очередного контейнера.
Пример входного файла:
7 9
2
18
47
16
38
55
48
Для такого набора контейнеров можно составить три блока, удовлетворяющих условию: (55, 38, 18, 2), (48, 16) и (47). Наибольшее количество контейнеров – в первом блоке – 4. Ответ: 3 4.
f = open(’26-101.txt’)
n, k = map(int, f.readline().split())
# Сортировка контейнеров по убыванию размера
a = sorted([int(i) for i in f], reverse=True)
bloks = [] # Список блоков
mx = 0 # Максимальное количество контейнеров в блоке
while a: # Пока список ’a’ не пустой
# Добавляем контейнер в новый блок и удаляем из списка ’a’
bloks.append([a.pop(0)])
for i in bloks[-1]: # Перебираем контейнеры в текущем блоке
for j in a: # Перебираем оставшиеся контейнеры
if i - j >= k: # Если разница между контейнерами не меньше ’k’
bloks[-1].append(j) # Добавляем контейнер в текущий блок
a.remove(j) # Удаляем контейнер из списка оставшихся
break # Переходим к следующему контейнеру
# Обновляем максимальное количество контейнеров в блоке
mx = max(mx, len(bloks[-1]))
# Kоличество блоков и максимальное количество контейнеров в одном блоке
print(len(bloks), mx)