26.06 Распределение объектов по местам (хранение багажа, парковки, кафе, гостиницы)
Ошибка.
Попробуйте повторить позже
Источник: https://kpolyakov.spb.ru/
В гостинице составляют недельный план уборки номеров после отъезда клиентов. Все номера одинаковые и
пронумерованы с 
до 
. В основе плана – журнал заявок, в каждой из которых записано время заезда и время выезда
для 
заявок. Заявки поступают в случайном порядке. На начало недели все номера подготовлены к заселению. После
отъезда клиента на уборку номера отводится 
минут. Уборка начинается в следующую минуту после освобождения
номера. Клиент может заезжать в подготовленный номер в следующую минуту после окончания уборки. Если
подготовленных номеров несколько, то выбирается номер с максимальным временем простоя; из номеров с
одинаковым временем простоя – последний номер. Если подготовленных номеров нет, клиент ждет первый подготовленный
номер; при этом время отъезда не меняется.
Определите максимальное время ожидания клиента перед заселением и последний номер, заселенный в течение этой недели.
Входные данные
В первой строке входных данных задается два числа: 
– количество номеров (
) и 
– количество
заявок (
). В каждой из последующих 
строк указано время заезда и время выезда в минутах, начиная с
воскресенья.
Выходные данные
Запишите в ответе два числа: максимальное время ожидания клиента перед заселением и последний номер, заселенный в течение этой недели.
Пример входного файла:
При таких исходных данных первый клиент в минуту 
сразу заезжает в номер 
, в 
-ю минуту второй клиент
заезжает в номер 
(без ожидания). На 
-й минуте первый клиент выезжает из номера 
и в этом номере сразу
начинается уборка, которая заканчивается на 
-й минуте. Поэтому третий клиент, который хотел заселиться на 
-й
минуте, будет ждать 
минуту и заселится в номер 
на 
-й минуте. Аналогично четвёртый клиент, который хотел
заселиться на 
-й минуте, должен ждать 
минут, потому что готовый номер 
будет готов только на
минуте. Последний клиент, желающий заселиться на 
-й минуте, фактически сможет сделать
это только на 
минуте, так что он будет ждать 40 минут и заселится в номер 
. Ответ:
.
with open(’26.txt’) as F: K, N = map(int, F.readline().split()) data = [tuple(map(int, F.readline().split())) for i in range(N)] data.sort() freeTime = [0] * K # время готовности maxWait = 0 lastRoom = -1 for tStart, tEnd in data: k = 0 for i in range(1, K): if freeTime[i] <= freeTime[k]: k = i maxWait = max(freeTime[k] - tStart, maxWait) if freeTime[k] <= tEnd and freeTime[k] < 7 * 24 * 60: print(tStart, tEnd, ’->’, k + 1, max(0, freeTime[k] - tStart)) freeTime[k] = max(freeTime[k], tEnd) + 31 lastRoom = k + 1 print(maxWait, lastRoom)
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
