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

Скоростной поезд, направляющийся из Москвы в Санкт-Петербург, ожидает пассажиров. Состав поезда включает в себя $K$ сцепленных пассажирских вагонов, каждый из которых содержит $M$ пассажирских мест. Вагоны и места в них нумеруются от 1 до $K$ и от 1 до $M$ соответственно.

Известен перечень, состоящий из $N$ заявок на бронь билетов на поезд за вчерашний день. В каждой из заявок указано время подачи заявки (в минутах от начала суток) и желаемый номер вагона и номер места в нём. Оператор обрабатывает заявки последовательно, начиная с ранее поданных (среди заявок, поданных в одинаковое время, прежде обрабатываются заявки с наименьшими указанными в них номерами вагонов и, если номера вагонов совпали, с наименьшими номерами мест в этих вагонах), и если указанное в заявке место в нужном вагоне ещё свободно, утверждает билет на это место, а иначе утверждает билет на наименьшее по номеру свободное место, расположенное в вагоне, который находится как можно ближе к кабине машиниста (вагон с кабиной машиниста имеет нулевой номер и не является пассажирским). Если же свободных мест нет, билет не утверждается.

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

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

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

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

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

2

2

7

1010 1 2

440 2 1

890 2 1

310 1 2

170 2 2

540 1 2

1390 2 1

При таких исходных данных билеты без изменений будут утверждены по заявкам №2, 4 и 5. Последний утвержденный билет по заявке №6 будет не соответствовать заявке (он будет определен на место №1 в вагоне №1, т.к. место №2 в вагоне №1 уже занято). Ответ: 1 2.

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

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