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

Просмотров 7 Комментарии 0

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

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

Определите минимальное количество ячеек, которые потребуются для хранения всех контейнеров, и максимальное количество контейнеров в одном блоке.

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

В первой строке входного файла записано число $N$ – количество контейнеров (натуральное число, не превышающее $20000$ ) и число $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$ .

n, k  = map(int, input().split())

all = []
for i in range(n):
    num = int(input())
    all.append(num)

all = sorted(all)[::-1]

ans = []

while True:
    if all[0] == 0:
        break

    # [длина, цвет]
    chain = [ all[0] ]
    all.pop(0)
    all.append(0)

    i = 0
    while i < len(all):
        if all[i] == 0:
            break

        if chain[-1] - all[i] >= k:
            chain.append(all[i])
            all.pop(i)
            all.append(0)
            i -= 1
        i += 1

    ans.append(chain)


print(len(ans), max( [len(x) for x in ans ] ))

Ответ: 19 1045