На вокзале есть камера хранения из K ячеек, которые пронумерованы с 1. Принимаемый багаж кладется в свободную ячейку с минимальным номером. Известно время, когда пассажиры сдают и забирают багаж (в минутах с начала суток). Ячейка доступна для багажа, начиная со следующей минуты, после окончания срока хранения. Если свободных ячеек не находится, то багаж не принимается в камеру хранения.
Найдите количество багажей, которое будет сдано в камеры за 24 часа и номер ячейки, в которую сдаст багаж последний пассажир.
Входные данные. В первой строке входного файла находится число K – количество ячеек в камере хранения, во второй строке файла число N – количество пассажиров, сдающих багаж (натуральное число, не превышающее 1000). Каждая из следующих N строк содержит два натуральных числа, не превышающих 1440: время сдачи багажа и время выдачи багажа.
Выходные данные Программа должна вывести два числа через пробел: количество сданных в камеру хранения багажей и номер ячейки, в которую примут багаж у последнего пассажира, который сможет сдать багаж.
Решение (Python)
f = open(’26_8__3mjzz.txt’)
k = int(f.readline()) # количество камер хранения
n = int(f.readline()) # количество пассажиров, сдающих багаж
# Создаём список, в котором будут храниться данные о времени,
# когда каждый пассажир собирается сдавать и забирать вещи
a=[list(map(int, i.split())) for i in f]
# Применяем сортировку, чтобы пассажиры приходили в том порядке, который задан временем их прихода
a.sort()
# Список с данными о каждой камере
cell=[-1]*k
count = 0 # Кол-во пассажиров, сдавших багаж
last = 0 # Номер камеры, в которую примут вещи у последнего пассажира
# Перебор пассажиров
for i in range(n):
# Проходимся по каждой камере
for j in range(len(cell)):
# Если из текущей камеры багаж заберут раньше,
# чем придёт пассажир, то помещаем багаж пассажира в эту камеру.
# В списке сохраняем время, когда пассажир должен забрать багаж из камеры.
if a[i][0]>cell[j]:
count+=1
cell[j]=a[i][1]
# Сохраняем номер последней ячейки
# (прибавляем единицу, так как нумерация камер с единицы, а не с нуля)
last=j+1
# Прерываем внутренний цикл, чтобы перейти к следующему пассажиру
break
print(count, last)