26.06 Распределение объектов по местам (хранение багажа, парковки, кафе, гостиницы)
Ошибка.
Попробуйте повторить позже
Входной файл содержит заявки пассажиров, желающих сдать свой багаж в камеру хранения. В заявке указаны время сдачи багажа (в минутах от начала суток) и время, на которое пассажир сдает багаж (в минутах).
Багаж одного пассажира размещается в одной свободной ячейке с минимальным номером. Ячейки пронумерованы начиная с единицы. Размещение багажа в ячейке или её освобождение происходит в течение 1 мин. Багаж можно поместить в только что освобождённую ячейку начиная со следующей минуты. Если в момент сдачи багажа свободных ячеек нет, то пассажир уходит. Если два пассажира приходят одновременно, приоритет будет у того, у кого время хранения багажа будет меньше.
Определите, сколько всего пассажиров не смогут оставить свой багаж в ячейках и общее время, в течение которого все ячейки будут заняты (без учета времени на разгрузку ячейки). Гарантируется, что все пассажиры, сдавшие багаж, заберут его в пределах 28 часов (время хранения каждого багажа не более 28 часов).
Входные данные. В первой строке входного файла находится число A – количество ячеек в камере хранения, во второй строке файла число B – количество пассажиров, сдающих багаж (натуральное число, не превышающее 1000). Каждая из следующих B строк содержит два натуральных числа: время сдачи багажа (не превышает 1600) и время хранения багажа (не превышает 1600).
Выходные данные. Запишите в ответе два числа через пробел: количество пассажиров, которые не смогли воспользоваться камерой хранения и общее время, в течении которого все ячейки будут заняты.
f = open(’26_6__3mk0m.txt’) k = int(f.readline()) n = int(f.readline()) t = [list(map(int, i.split())) for i in f] # Сортируем пассажиров по времени сдачи багажа t.sort() # Создаем список камер хранения, где каждая камера - это список пар storage = [[] for i in range(k)] time = [0 for i in range(3500)] # Перебираем всех пассажиров в отсортированном порядке for i in t: # Проверяем каждую камеру начиная с 0 for j in range(k): # Если камера пуста ИЛИ время сдачи текущего пассажира > времени выдачи # последнего в этой камере if (not storage[j]) or (i[0] > storage[j][-1]): storage[j].append(i[0]+i[1]) # Добавляем пассажира в эту камеру for minute in range(i[0], i[0] + i[1]): time[minute] += 1 # отмечаем под каждой минутой, что на одну камеру стало занято больше break # Переходим к следующему пассажиру count = sum([len(i) for i in storage]) count_minute = 0 # количество минут, в течении которых были заняты все камеры for i in time: # проход по отрезку времени if i == k: # если количество занятых камер равно количеству камер в файле count_minute += 1 # увеличиваем счётчик минут, в течении которого были заняты все камеры # количество людей, которые не смогли положить вещи можно посчитать следующим образом: # общее кол-во людей - кол-во людей положивших вещи в камеру print(n - count, count_minute)
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
