Задание 26 ЕГЭ по информатике · 290F15

Задание выполняется с использованием прилагаемых файлов. Входной файл содержит заявки пассажиров, желающих сдать свой багаж в камеру хранения. В заявке указаны время сдачи багажа и время освобождения ячейки в минутах от начала суток. Багаж одного пассажира размещается в одной свободной ячейке с минимальным номером. Ячейки пронумерованы начиная с единицы. Размещение багажа в ячейке или её освобождение происходит в течение 1 мин. Багаж можно поместить в только что освобождённую ячейку начиная со следующей минуты. Если в момент сдачи багажа свободных ячеек нет, пассажир уходит. Определите, сколько пассажиров сможет сдать свой багаж в течение 24 ч и какой номер будет иметь ячейка, которую займут последней. Если таких ячеек несколько, укажите минимальный номер ячейки.
В первой строке входного файла находится натуральное число K, не превышающее 1000, — количество ячеек в камере хранения. Во второй строке находится натуральное число N, не превышающее 1000, — количество пассажиров. Каждая из следующих N строк содержит два натуральных числа, каждое из которых не превышает 1440: указанное в заявке время размещения багажа в ячейке и время освобождения ячейки.

1. Создаём массив времени освобождения ячеек. Изначально все ячейки свободны; это можно обозначить временем освобождения 0.

2. Заявки обрабатываются в порядке, указанном во входном файле. Для заявки с временем сдачи багажа t просматриваем ячейки по возрастанию номеров.

3. Ячейка свободна для новой заявки, если её время освобождения строго меньше t. Это учитывает условие, что воспользоваться только что освобождённой ячейкой можно начиная со следующей минуты.

4. Если подходящая ячейка найдена, размещаем в ней багаж, записываем её новое время освобождения, увеличиваем количество обслуженных пассажиров и обновляем минимальный номер среди ячеек, занятых последними.