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

Входной файл содержит заявки пассажиров, желающих сдать свой багаж в камеру хранения. В заявке указаны вес, время сдачи багажа и время освобождения ячейки (в минутах от начала суток). Багаж одного пассажира размещается в одной свободной и подходящей по вместимости для хранения багажа ячейке с минимальным номером (это правило работает для всех пассажиров, кроме того, который сдаст свой багаж последним – он может выбрать любую свободную ячейку, в которую вмещается его багаж). Ячейки пронумерованы, начиная с единицы. Размещение багажа в ячейке или её освобождение происходит в течение 1 минуты. Багаж можно поместить в только что освобождённую ячейку, начиная со следующей минуты. Если в момент сдачи багажа свободных и подходящих ячеек нет, то пассажир уходит. Среди одновременно пришедших первыми обслуживаются пассажиры с меньшим весом багажа и, если вес одинаковый, с самым ранним временем освобождения ячейки.

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

Входные данные

В первой строке входного файла находится натуральное число $K$, не превышающее 1000, – количество ячеек в камере хранения. Во второй строке – натуральное число $N$ ($N ≤ 10000$), обозначающее количество пассажиров. В третьей строке записаны $K$ натуральных чисел, обозначающих вместимости соответственно пронумерованных слева направо ячеек. Каждая из следующих $N$ строк содержит три натуральных числа: вес багажа, указанное в заявке время размещения багажа в ячейке и время освобождения ячейки (в минутах от начала суток).

Запишите в ответе два числа: количество пассажиров, которые смогут воспользоваться камерой хранения, и максимально возможный номер последней занятой ячейки.

Типовой пример организации данных во входном файле

2

5

100 200

150 30 60

301 40 1000

170 59 60

40 61 1000

80 1010 1440

При таких исходных данных положить вещи в камеру хранения смогут первый, четвёртый и пятый пассажиры. Последний пассажир положит вещи в ячейку 2, так как ячейки 1 и 2 будут свободны и обе подходят по критерию вместимости багажа. Ответ: 3 2.

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.

Файл к заданию: https://storage.yandexcloud.net/100points-bank/informatics-ege/files/12187_26.txt