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