Тема 26. Обработка целочисленной информации с использованием сортировки
26.07 Прочие прототипы
Вспоминай формулы по каждой теме
Решай новые задачи каждый день
Вдумчиво разбирай решения
ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!
Подтемы раздела обработка целочисленной информации с использованием сортировки
Решаем задачу:

Ошибка.
Попробуйте повторить позже

Задача 1#87925

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

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

б) цвета внешнего и внутреннего контейнеров различны. Группу вложенных друг в друга контейнеров называют блоком. Количество контейнеров в блоке может быть любым.

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

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

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

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

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

Вложения к задаче
Показать ответ и решение
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)

Ответ: 1128 12

Специальные программы

Все специальные программы

Программа
лояльности v2.0

Приглашай друзей в Школково и получай вознаграждение до 10%!

Крути рулетку
и выигрывай призы!

Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.

Бесплатное обучение
в Школково

Для детей ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Брянской областей, а также школьникам, находящимся в пунктах временного размещения Крыма обучение на платформе бесплатное.

Налоговые вычеты

Узнай, как получить налоговый вычет при оплате обучения в «Школково».

Специальное предложение
для учителей

Бесплатный доступ к любому курсу подготовки к ЕГЭ или олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!

Вернём деньги за курс
за твою сотку на ЕГЭ

Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!

cyberpunkMouse
cyberpunkMouse
Рулетка
Вы можете получить скидку в рулетке!