Входной файл содержит заявки пассажиров, желающих сдать свой багаж в камеру хранения. В заявке указаны время сдачи багажа (в минутах от начала суток) и время, на которое пассажир сдает багаж (в минутах).
Багаж одного пассажира размещается в одной свободной ячейке с минимальным номером. Ячейки пронумерованы начиная с единицы. Размещение багажа в ячейке или её освобождение происходит в течение 1 мин. Багаж можно поместить в только что освобождённую ячейку начиная со следующей минуты. Если в момент сдачи багажа свободных ячеек нет, то пассажир уходит. Если два пассажира приходят одновременно, приоритет будет у того, у кого время хранения багажа будет меньше.
Определите, сколько всего пассажиров не смогут оставить свой багаж в ячейках и общее время, в течение которого все ячейки будут заняты (без учета времени на разгрузку ячейки). Гарантируется, что все пассажиры, сдавшие багаж, заберут его в пределах 24 часов (время хранения каждого багажа не более 24 часов).
Входные данные. В первой строке входного файла находится число A – количество ячеек в камере хранения, во второй строке файла число B – количество пассажиров, сдающих багаж (натуральное число, не превышающее 1000). Каждая из следующих B строк содержит два натуральных числа: время сдачи багажа (не превышает 1600) и время хранения багажа (не превышает 1600).
Запишите в ответе два числа через пробел: количество пассажиров, которые не смогли воспользоваться камерой хранения и общее время, в течении которого все ячейки будут заняты.
file = open(’26_6__3mk0m.txt’)
count_cameras = int(file.readline()) # количество камер хранения
count_client = int(file.readline()) # количество пассажиров
array_client = sorted(list(map(int,i.split())) for i in file)
cameras = [-1]*count_cameras # камеры хранения. каждый элемент списка - это камера хранения.
# в ячейки будем записывать время освобождения определенной камеры хранения
count = 0 # количество человек, которые смогли положить вещи в камеру хранения
# временной промежуток от 0 до 3500 минут. Каждый элемент списка это определенная минута.
# Значение под определенной ячейкой - это количество занятых камер в данную минуту
time = [0 for i in range(3500)]
count_minute = 0 # количество минут, в течении которых были заняты все камеры
for client in array_client: # проход по клиентам
for i in range(len(cameras)): # проход по камерам хранения
# если время прихода текущего клиента больше чем время освобождения данной камеры
if client[0] > cameras[i]:
cameras[i] = client[0]+client[1] # тогда записываем время освобождения данной камеры текущим клиентом
count += 1
# проходимся по минутам от времени прихода до времени ухода текущего клиента
for minute in range(client[0],client[0]+client[1]):
time[minute] += 1 # отмечаем под каждой минутой, что на одну камеру стало занято больше
break # прерываем цикл, так как текущий клиент уже положил свои вещи и переходим к следующему клиенту
for i in time: # проход по отрезку времени
if i == count_cameras: # если количество занятых камер равно количеству камер в файле
count_minute += 1 # увеличиваем счётчик минут, в течении которого были заняты все камеры
# количество людей, которые не смогли положить вещи можно посчитать следующим образом:
# общее кол-во людей - кол-во людей положивших вещи в камеру
print(count_client- count,count_minute)