26.06 Распределение объектов по местам (хранение багажа, парковки, кафе, гостиницы)
Готовиться с нами - ЛЕГКО!
Ошибка.
Попробуйте повторить позже
В новом городе Подмосковске открылся новый ресторан - Кафеск. В нем есть А столиков. После каждого клиента, посетившего ресторан, необходимо убрать столик, на это уходит 8 минут. Уборка начинается в следующую минуту после ухода клиента. Новый клиент может сесть в следующую минуту после завершения уборки. Ресторан работает с 8:00 и закрывается в 22:30. Все клиенты должны уйти не позже 22:30. За это время в него приходит В клиентов. (Гарантируется, что они придут не раньше 8:00, а планируют уйти не позже 22:30).
Каждого гостя при входе встречает администратор и подбирает для него стол с минимальным номером. Может случиться так, что несколько людей придет одновременно, тогда администратор в первую очередь подбирает столик для того, кто планирует сидеть меньшее время. В случае если все столы заняты, гость готов подождать не более 45 минут, при этом за столом он пробудет обязательно T минут (T – разница между временем прибытия и отбытия), в этом случае выбирается столик, который освободится раньше всего. Если таких несколько, выбирается с меньшим номером.
Определите, сколько клиентов получится обслужить за время работы ресторана и номер клиента, который последний сможет сесть за столик. (Клиентов считают с начала дня начиная с 1). В ответ запишите числа через пробел.
Входные данные: На первой строке одно число В – количество гостей, пришедших за день. На второй строке одно число А – количество столиков в ресторане. Далее В строк, в каждой из которых указано время, когда клиент пришел и время, до которого он планировал пробыть в ресторане (время дано в минутах от начала дня).
f = open(’26_dif_4.txt’)
n = int(f.readline())
k = int(f.readline())
clients = [list(map(int, i.split())) for i in f]
clients.sort()
tables = [-1] * k
cnt = 0
number = 0
client_num = 0
for start, end in clients:
# Считаем клиентов, у первого номер 1
number += 1
is_sat = False
for i in range(k):
if start >= tables[i]:
# Пример: предыдущий клиент уходит в 10-ю минуту
# В 11-ю минуту начинается освобождение
# Освобождение длится 8 минут: 11-я, 12-я, 13-я, 14-я, 15-я, 16-я, 17-я, 18-я
# В 19-ю минуту может занять следующий клиент
# Значит, если в условии не строгий знак, то прибавлять нужно 9
tables[i] = end + 9
is_sat = True
cnt += 1
client_num = number
break
if not is_sat:
# Минимальное время освобождения столика
min_time = min(tables)
if start + 45 >= min_time:
# Индекс столика с минимальным временем в нашем списке
index = tables.index(min_time)
# Время пребывания клиента за столом
T = end - start
# Проверяем, что клиент уйдёт до закрытия
# 22 * 60 + 30 - это 22:30
if tables[index] + T <= 22 * 60 + 30:
tables[index] += T + 9
cnt += 1
client_num = number
print(cnt, client_num)
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
