26.09 Прочие прототипы
Ошибка.
Попробуйте повторить позже
На складе требуется разместить 
контейнеров различного размера, каждый из которых имеет форму куба.
Контейнеры имеют разные цвета, которые обозначаются латинскими буквами. Чтобы сэкономить место,
контейнеры вкладывают друг в друга. Один контейнер можно вложить в другой, если выполнены следующие
условия:
а) размер стороны внешнего контейнера превышает размер стороны внутреннего на 
и более условных
единиц
б) цвета внешнего и внутреннего контейнеров различны. Группу вложенных друг в друга контейнеров называют блоком. Количество контейнеров в блоке может быть любым.
Каждый блок, независимо от количества и размера входящих в него контейнеров, а также каждый одиночный контейнер, не входящий в блоки, занимает при хранении одну складскую ячейку.
Определите минимальное количество ячеек, которые потребуются для хранения всех контейнеров, и максимальное количество контейнеров в одном блоке.
Входные данные:
В первой строке входного файла записано натуральное число 
– количество контейнеров,
натуральное число 
– наименьшая допустимая разница размеров вложенных соседних
контейнеров
Каждая из следующих 
строк содержит натуральное число, не превышающее 
– длину стороны очередного
контейнера, и латинскую букву, обозначающую цвет этого контейнера.
Пример:
Для такого набора контейнеров можно составить два блока, удовлетворяющих условию: 
, 
.
Наибольшее количество контейнеров – в первом блоке – 
. Ответ: 
.
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 ] ))
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
