Задача к ЕГЭ по информатике на тему «Распределение объектов по местам (хранение багажа, парковки, кафе, гостиницы)» №1

Источник: https://kpolyakov.spb.ru/

В гостинице составляют недельный план уборки номеров после отъезда клиентов. Все номера одинаковые и пронумерованы с $1$ до $K$ . В основе плана – журнал заявок, в каждой из которых записано время заезда и время выезда для $N$ заявок. Заявки поступают в случайном порядке. На начало недели все номера подготовлены к заселению. После отъезда клиента на уборку номера отводится $30$ минут. Уборка начинается в следующую минуту после освобождения номера. Клиент может заезжать в подготовленный номер в следующую минуту после окончания уборки. Если подготовленных номеров несколько, то выбирается номер с максимальным временем простоя; из номеров с одинаковым временем простоя – последний номер. Если подготовленных номеров нет, клиент ждет первый подготовленный номер; при этом время отъезда не меняется.

Определите максимальное время ожидания клиента перед заселением и последний номер, заселенный в течение этой недели.

Входные данные

В первой строке входных данных задается два числа: $K$ – количество номеров ( $1 ≤ K ≤ 1000$ ) и $N$ – количество заявок ( $1 ≤ N ≤ 100000$ ). В каждой из последующих $N$ строк указано время заезда и время выезда в минутах, начиная с $0 : 00$ воскресенья.

Выходные данные

Запишите в ответе два числа: максимальное время ожидания клиента перед заселением и последний номер, заселенный в течение этой недели.

Пример входного файла:

$2 5$

$10 30$

$15 40$

$40 65$

$55 80$

$56 100$

При таких исходных данных первый клиент в минуту $10$ сразу заезжает в номер $2$ , в $15$ -ю минуту второй клиент заезжает в номер $1$ (без ожидания). На $30$ -й минуте первый клиент выезжает из номера $2$ и в этом номере сразу начинается уборка, которая заканчивается на $60$ -й минуте. Поэтому третий клиент, который хотел заселиться на $40$ -й минуте, будет ждать $21$ минуту и заселится в номер $2$ на $61$ -й минуте. Аналогично четвёртый клиент, который хотел заселиться на $55$ -й минуте, должен ждать $16$ минут, потому что готовый номер $1$ будет готов только на $40 +30 + 1 = 71$ минуте. Последний клиент, желающий заселиться на $56$ -й минуте, фактически сможет сделать это только на $65+ 30 +1 = 96$ минуте, так что он будет ждать 40 минут и заселится в номер $2$ . Ответ: $402$ .

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)

Ответ: 107 11