В магазине есть N камер хранения. В магазин приходят покупатели и оставляют свои вещи в камерах хранения. Покупатель занимает одну из камер с минимальным номером. Нумерация камер начинается с 1. Следующий покупатель может занять камеру хранения со следующей минуты после освобождения камеры. Освобождение начинается в следующую минуту после того, как покупатель забирает свои вещи, и длится 5 минут. Время, которое занята ячейка, не учитывает время освобождения ячейки и равняется разности времени ухода и времени прибытия клиента. Известно время сдачи вещей каждого покупателя и время выдачи вещей каждому покупателю. Если свободных камер нет, то покупатели уходят. Если в один момент пришло несколько покупателей, то сначала вещи в камеру положит клиент, у которого меньшее количество времени вещи будут находиться в камере.
Входные данные: В первой строке файла находится натуральное число N – количество покупателей. Во второй строке файла находится натуральное число K – количество камер хранения в магазине. В последующих строках записано по два числа, не превышающих 1500: время прибытия клиента, время ухода клиента.
Запишите в ответ два числа через пробел: количество покупателей, которые не смогут сдать вещи в камеры хранения, и количество минут, которое суммарно будут заняты ячейки.
Решение (Python)
f = open(’26_dif_3__40zrx.txt’)
n = int(f.readline())
k = int(f.readline())
clients = [list(map(int, i.split())) for i in f]
clients.sort()
cameras = [-1] * k # список, симулирующий каждую камеру хранения, в котором будет записано время, в которое освободится каждое место
cnt = 0
sm = 0
for start, end in clients: # проход по клиентам
for j in range(k): # проход по камерам хранения
if start > cameras[j]:
# Пример: предыдущий клиент уходит в 10-ю минуту
# В 11-ю минуту начинается освобождение
# Освобождение длится 5 минут: 11-я, 12-я, 13-я, 14-я, 15-я
# В 16-ю минуту может занять следующий клиент
# Значит, если в условии строгий знак, то прибавлять нужно 5
cameras[j] = end + 5
cnt += 1
sm += end - start # суммируем время, в течении которого вещь будет находиться в камере
break # сбрасываем цикл - переходим к следующему клиенту
print(n - cnt, sm)