В Москве открылся новый ресторан. В нем есть А столиков. После каждого клиента столик необходимо убрать, на это уходит 15 минут. Уборка начинается через две минуты после того, как уходит гость. Новый клиент может сесть в следующую минуту после завершения уборки. Ресторан работает с 7:00 и закрывается в 21:00. Все клиенты должны уйти не позже 21:00. За это время в него приходит В клиентов. (Гарантируется, что они придут не раньше 7:00, а планируют уйти не позже 21:00).
Каждого гостя при входе встречает администратор и подбирает для него стол с минимальным номером. Может случиться так, что несколько людей придет одновременно, тогда администратор в первую очередь подбирает столик для того, кто планирует сидеть меньшее время. В случае если все столы заняты, гость готов подождать не более 30 минут, при этом за столом он пробудет обязательно T минут (T – разница между временем прибытия и отбытия), в этом случае выбирается столик, который освободится раньше всего. Если таких несколько, выбирается с меньшим номером.
Определите, сколько клиентов получится обслужить за время работы ресторана и номер столика, за который сядет последний клиент. В ответе числа укажите через пробел.
Входные данные:
На первой строке одно число В – количество гостей, пришедших за день. На второй строке одно число А – количество столиков в ресторане. Далее В строк, в каждой из которых указано время, когда клиент пришел и время, до которого он планировал пробыть в ресторане (время дано в минутах от начала дня).
Решение (Python)
f=open(’26_10__30v17.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 = [0]*k # список, симулирующий каждое рабочее место, в котором будет записано время, в которое освободится каждое место
ans1=0
ans2=0
# проход по клиентам
for client in clients:
ok = False # флаг, которые показывает нужно ли человеку ждать или нет
# проход по всем столикам
for i in range(k):
# если время прихода текущего клиента больше чем время освобождения данного места другим клиентом и при этом текущий клиент уйдёт ранее закрытия магазина и придет позже или во время открытия
if client[0]>table[i] and client[0] >= 420 and client[1] <= 60*21:
table[i]=client[1]+17 # записываем время ухода текущего клиента с учётом уборки данного места после него
ok = True # помечаем, что для текущего клиента нашли место
ans1+=1 # увеличиваем счётчик пришедших клиентов
ans2=i+1 # запоминаем номер места, куда сел последний клиент
break # прерываем цикл - переходим к следующему клиенту
if not ok: # если клиенту нужно подождать
mt=min(table) # определяем место, которое освободится в ближайшее время
mintime=mt-client[0]+1 # определяем время, которое человеку нужно подождать прежде чем сесть за него
if mintime<=30: # если время ожидания не более 30 минут
ind=table.index(mt) # определяем индекс данного места в списке
T=client[1]-client[0] # считаем время T
if table[ind]+1+T<=1260: # если данный клиент уйдёт не позже закрытия
table[ind]+=2+T+15+1 # то сажаем данного человека за место
ans1+=1 # увеличиваем счётчик пришедших клиентов
ans2=ind+1 # запоминаем номер места, куда сел последний клиент
print(ans1,ans2)