#P1499. [CTSC2000] 公路巡逻
[CTSC2000] 公路巡逻
题目描述
在一条没有分岔的高速公路上有 个关口,相邻两个关口之间的距离都是 。所有车辆在这条高速公路上的最低速度为 ,最高速度为 ,并且只能在关口处改变速度。
巡逻的方式是在某个时刻 从第 个关口派出一辆巡逻车匀速驶抵第 个关口,路上耗费的时间为 秒。
两辆车相遇是指它们之间发生超车或者两车同时到达某关口(同时出发不算相遇)。
巡逻部门想知道一辆于 点整从第 个关口出发去第 个关口的车(称为目标车)最少会与多少辆巡逻车相遇,请编程计算之。假设所有车辆到达关口的时刻都是整秒。
输入格式
输入文件第一行为两个整数,分别为关口数 和巡逻车数 。
接下来的 行每一行为一辆巡逻车的信息(按出发位置递增排序),格式为 ,,,分别表示第 辆巡逻车的出发位置、出发时刻和路上耗费的时间,其中 和 为整数, 形如 HHMMSS
,表示时、分、秒,采用 小时制,不足两位的数用前置 补齐。
输出格式
输出文件第一行为目标车与巡逻车相遇次数。
第二行为目标车与巡逻车相遇次数最少时最早到达第 个关口的时刻(格式同输入中的 )。
3 2
1 060000 301
2 060300 600
0
061301
提示
,,,,所有的 不早于 ,不晚于 。
CTSC2000 第一试