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