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