26.06 Распределение объектов по местам (хранение багажа, парковки, кафе, гостиницы)
Ошибка.
Попробуйте повторить позже
В некотором салоне красоты есть К мест для процедур. После каждого клиента место необходимо убрать, на это уходит 10 минут. Уборка начинается в следующую минуту после того, как уходит клиент. Новый клиент может сесть в следующую минуту после завершения уборки. Салон работает с 7:00 и закрывается в 24:00. Все клиенты должны уйти не позже 24:00. За это время в него приходит N клиентов. При этом гарантируется, что они придут не раньше 7:00, а планируют уйти не позже 24:00.
Каждого клиента при входе встречает администратор и подбирает для него место с минимальным номером. Может случиться так, что несколько людей придет одновременно, тогда администратор в первую очередь подбирает место для того, кто планирует сидеть меньшее время. В случае если все места заняты, клиент готов подождать не более 20 минут, при этом за местом он пробудет обязательно T минут (T – разница между временем прибытия и отбытия), в этом случае выбирается место, которое освободится раньше всех. Если мест несколько, выбирается с меньшим номером.
Входные данные. На первой строке одно число N – количество клиентов, пришедших за день. На второй строке одно число K – количество мест в салоне. Далее N строк, в каждой из которых указано время, когда клиент пришел и время, до которого он планировал пробыть в салоне (время дано в минутах от начала дня).
Определите, сколько клиентов получится обслужить за время работы салона и номер места, за который сядет последний клиент. Числа в ответе запишите через пробел.
f=open(’26_7__1vn9f.txt’) n=int(f.readline()) # считываем количество пришедших клиентов k=int(f.readline()) # считываем количество мест в салоне clients = [] # список клиентов for line in f.readlines(): a,b=map(int, line.split()) clients.append([a,b]) clients.sort() # сортируем список клиентов table = [-1]*k # список, симулирующий каждое рабочее место, в котором будет записано время, в которое освободится каждое место ans1=0 ans2=0 for client in clients: # проход по каждому клиенту ok = False # флаг, которые показывает нужно ли человеку ждать или нет for i in range(k): # проход по всем рабочим местам в салоне # если время прихода текущего клиента больше чем время освобождения данного места другим клиентом и при этом текущий клиент уйдёт ранее закрытия магазина if client[0]>table[i] and client[1] <= 1440: table[i]=client[1]+10 # записываем время ухода текущего клиента с учётом уборки данного места после него ok = True # помечаем, что для текущего клиента нашли место ans1+=1 # увеличиваем счётчик пришедших клиентов ans2+=i+1 # запоминаем номер места, куда сел последний клиент break # прерываем цикл - переходим к следующему клиенту if not ok: # если клиенту нужно подождать mt=min(table) # определяем место, которое освободится в ближайшее время mintime=mt-client[0]+1 # определяем время, которое человеку нужно подождать прежде чем сесть за него # если время ожидания не более 20 минут if mintime<=20: ind=table.index(mt) # определяем индекс данного места в списке T=client[1]-client[0] # считаем время T if table[ind]+1+T<=1440: # если данный клиент уйдёт не позже закрытия table[ind]+=1+T+10 # то сажаем данного человека за место ans1+=1 # увеличиваем счётчик пришедших клиентов ans2=ind+1 # запоминаем номер места, куда сел последний клиент print(ans1,ans2)
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
