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

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

а) размер стороны внешнего контейнера превышает размер стороны внутреннего на $K$ и более условных единиц

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

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

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

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

В первой строке входного файла записано натуральное число $N$ $(1 ≤ N ≤ 20000)$ – количество контейнеров, натуральное число $K$ $(1 ≤ K ≤ 1000)$ – наименьшая допустимая разница размеров вложенных соседних контейнеров

Каждая из следующих $N$ строк содержит натуральное число, не превышающее $10000$ – длину стороны очередного контейнера, и латинскую букву, обозначающую цвет этого контейнера.

Пример:

$7 5$

$2 A$

$18 B$

$47 A$

$16 B$

$38 A$

$55 A$

$48 B$

Для такого набора контейнеров можно составить два блока, удовлетворяющих условию: $(55,48,38,18,2)$ , $(47,16)$ . Наибольшее количество контейнеров – в первом блоке – $5$ . Ответ: $2$ $5$ .

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

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

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

ans = []

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

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

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

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

    ans.append(chain)


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

Ответ: 25 2093