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

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

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

б) цвета внешнего и внутреннего контейнеров различны.

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

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

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

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

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

Пример:

$7 5 3$

$2 A$

$18 B$

$47 A$

$16 B$

$38 A$

$55 A$

$48 B$

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

n, k, m = 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
        if len(chain) == m:
            break

    ans.append(chain)


print(len(ans), sum( [1 for x in ans if len(x) == m] ))

Ответ: 678 657