Задача к ЕГЭ по информатике на тему «задачи под вебы» №35

Задача с сайта https://kpolyakov.spb.ru/

На складе требуется разместить N  контейнеров различного размера, каждый из которых имеет форму куба. Чтобы сэкономить место, контейнеры вкладывают друг в друга. Один контейнер можно вложить в другой, если размер стороны внешнего контейнера превышает размер стороны внутреннего на K  и более условных единиц. Группу вложенных друг в друга контейнеров называют блоком. Количество контейнеров в блоке может быть любым. Каждый блок, независимо от количества и размера входящих в него контейнеров, а также каждый одиночный контейнер, не входящий в блоки, занимает при хранении одну складскую ячейку. Определите минимальное количество ячеек, которые потребуются для хранения всех контейнеров, и максимальное количество контейнеров в одном блоке.

Входные данные представлены в файле 26-101.txt следующим образом. В первой строке входного файла записано число N  – количество контейнеров (натуральное число, не превышающее 20 000) и число K  (1 ≤ K ≤ 1000  ) – наименьшая допустимая разница размеров вложенных соседних контейнеров. Каждая из следующих N  строк содержит одно натуральное число, не превышающее 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)

Ответ: 19 1045
Оцените статью
Я решу все!