Ошибка.
Попробуйте повторить позже
На складе требуется разместить контейнеров различного размера, каждый из которых имеет форму куба. Контейнеры имеют разные цвета, которые обозначаются латинскими буквами. Чтобы сэкономить место, контейнеры вкладывают друг в друга. Один контейнер можно вложить в другой, если выполнены следующие условия:
а) размер стороны внешнего контейнера превышает размер стороны внутреннего на и более условных единиц.
б) цвета внешнего и внутреннего контейнеров различны. Группу вложенных друг в друга контейнеров называют блоком. Количество контейнеров в блоке может быть любым.
Каждый блок, независимо от количества и размера входящих в него контейнеров, а также каждый одиночный контейнер, не входящий в блоки, занимает при хранении одну складскую ячейку.
Определите минимальное количество ячеек, которые потребуются для хранения всех контейнеров, и количество контейнеров цвета А в блоке с максимальным количеством контейнеров. Если таких блоков несколько, выведите максимальное встреченное в них количество контейнеров цвета А.
Входные данные:
В первой строке входного файла записано натуральное число – количество контейнеров, натуральное число – наименьшая допустимая разница размеров вложенных соседних контейнеров
Каждая из следующих строк содержит натуральное число, не превышающее – длину стороны очередного контейнера, и латинскую букву, обозначающую цвет этого контейнера.
f = open(’26_dif_5.txt’) n, k = map(int, f.readline().split()) containers = [] for s in f: size, color = s.split() containers.append([int(size), color]) # Сортируем по убыванию первого и возрастанию второго элемента. # Сортировка по возрастанию второго элемента для того, # чтобы в первую очередь рассматривались контейнеры A. containers.sort(key=lambda x: (-x[0], x[1])) # Количество собранных блоков cnt = 0 # Количество контейнеров цвета А в максимальном блоке color_A = 0 # Размер максимального блока mx = 0 while len(containers) > 0: cnt += 1 # Выбранные контейнеры chosen = [containers[0]] # Не выбранные контейнеры not_chosen = [] # Количество контейнеров А A = 1 if containers[0][1] == ’A’ else 0 for cont in range(1, len(containers)): size, color = containers[cont] # Если размер предыдущего отличается от размера текущего не менее чем на k # А также цвета различны if chosen[-1][0] - size >= k and chosen[-1][1] != color: chosen.append(containers[cont]) if color == ’A’: A += 1 else: not_chosen.append(containers[cont]) if len(chosen) > mx: mx = len(chosen) color_A = A elif len(chosen) == mx: color_A = max(color_A, A) # Обновляем список, чтобы в нём не было выбранных уже контейнеров containers = list(not_chosen) print(cnt, color_A)
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное обучение
в Школково
Для детей ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Брянской областей, а также школьникам, находящимся в пунктах временного размещения Крыма обучение на платформе бесплатное.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ или олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!