26.06 Распределение объектов по местам (хранение багажа, парковки, кафе, гостиницы)
Ошибка.
Попробуйте повторить позже
Источник: https://kpolyakov.spb.ru/
На парковке расположены парковочные места для 
категорий автомобилей. Номер категории – целое
неотрицательное число, меньшее, чем 
. Для каждой категории автомобилей выделено некоторое количество
парковочных мест. Приезжающий на парковку автомобиль занимает любое свободное место среди мест, предназначенных
для автомобилей его категории, а также среди мест, предназначенных для автомобилей c б´oльшим номером категории.
Автомобиль всегда паркуется на подходящем свободном месте для автомобилей с наименьшей категорией.
Если подходящего свободного места нет, автомобиль уезжает. Гарантируется, что никакие два автомобиля
не приезжают одновременно. Если время прибытия автомобиля совпадает со временем окончания стоянки
другого автомобиля, вновь прибывший автомобиль может занять освободившееся место, если оно подходит
ему.
Пусть 
– минимальный номер категории парковочных мест, в которой за всё время припарковалось
наибольшее количество автомобилей. Определите время, через которое освободятся (и больше не будут заняты) все
парковочные места категории 
, и количество автомобилей, которые парковались на местах категории
.
Входные данные
Первая строка входного файла содержит два натуральных числа, записанных через пробел: 
– количество категорий
автомобилей, 
M
, и 
– общее количество автомобилей, приехавших на парковку в течение одного года,
N
. Вторая строка содержит M чисел – количество парковочных мест на стоянке для автомобилей каждой
категории, начиная с категории под номером 
, в порядке возрастания номеров категорий. Каждое из этих чисел не
превышает 
. Каждая из 
последующих строк описывает один автомобиль и содержит три целых числа: время в
минутах с начала года, когда автомобиль прибыл на парковку; необходимую длительность стоянки в минутах и номер
категории автомобиля.
Выходные данные
В ответе запишите два целых числа: время освобождения парковочных мест категории 
, затем – общее количество
автомобилей, которые парковались на местах категории 
.
Пример входного файла:
При таких исходных данных: 
-й автомобиль (категории 
) припаркуется на месте категории 
с 
по 
минуты,
-й автомобиль (категории 
) припаркуется на месте категории 
с 
по 
минуты, 
-й автомобиль (категории 
)
припаркуется на месте категории 
с 
по 
минуты, 
-й автомобиль (категории 
) не найдет место, 
-й
автомобиль (категории 
) не найдет место. В категории мест с номером 
припарковалось максимальное
количество автомобилей – 
, все парковочные места категории 
освободились на 
-й минуте. Ответ:
.
Решение (Python)
file = open(’Задание_27__1vtrl.txt’) # считываем количество машин в файле count_category,count_cars = map(int,file.readline().split()) # Количество парковочных мест для каждой категории all_category = list(map(int,file.readline().split())) cars = [] # список, в котором будут записаны машины for i in range(count_cars): start,duration,type = map(int,file.readline().split()) cars.append([start,duration,type]) # добавляем запись о машине в список cars.sort() # сортируем список # симулируем парковку, списки парковочных мест для каждой категории parking = [] for i in range(count_category): parking.append([-1 for i in range(all_category[i])]) # добавление парковочных мест для определенной категории count = [0 for i in range(count_category)] for start,duration,category in cars: # перебор машин в списке # флаг, который показывает нашли мы ли место для парковки для текущей машины или нет. # Это сделано, с той целью, чтобы позже сбросить циклы перебора категории и перебор парковочных мест определенной категории. ok = False # перебираем категорию для парковочного места for categ in range(category,count_category): # перебираем парковочные места определенной категории for i in range(len(parking[categ])): # если время приезда текущей машины совпадает или больше времени уезда той, что уже припаркована на данном парковочном месте if start >= parking[categ][i]: parking[categ][i] = start + duration # то припарковываем текущую машину на это парковочное место count[categ] += 1 # увеличиваем количество припаркованных машин на парковочном месте определенной категории ok = True # отмечаем, что машину припарковали break # сбрасываем цикл, переходим к следующей категории if ok: # если текущую машину припарковали break # то сбрасываем цикл, чтобы перейти к следующей машине # Вывод освобождения парковочных мест категории, в которой припарковалось больше всего машин print(max(parking[count.index(max(count))])) # Вывод количества машин, которые припарковались на категории парковочных мест где припарковалось больше всего машин print(max(count))
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
