网站页面
当前课程
成员
General
主题 1
主题 2
主题 4
主题 5
主题 6
主题 7
主题 8
主题 9
主题 10
主题 11
主题 12
主题 13
主题 14
主题 15
主题 16
主题 17
主题 18
主题 19
主题 20
[CTSC2000]公路巡逻
成绩 | 开启时间 | 2014年09月19日 星期五 10:08 | |
折扣 | 0.8 | 折扣时间 | 2014年09月26日 星期五 10:08 |
允许迟交 | 是 | 关闭时间 | 2014年09月26日 星期五 10:08 |
输入文件 | patrol.in | 输出文件 | patrol.out |
【题目描述】
在一条没有分岔的高速公路上有n个关口,相邻两个关口之间的距离都是10km。所有车辆在这条高速公路上的最低速度为60km/h,最高速度为120km/h,并且只能在关口处改变速度。
巡逻的方式是在某个时刻Ti从第ni个关口派出一辆巡逻车匀速驶抵第(ni+1)个关口,路上耗费的时间为ti秒。两辆车相遇是指它们之间发生超车或者两车同时到达某关口(同时出发不算相遇)。
巡逻部门想知道一辆于6点整从第1个关口出发去第n个关口的车(称为目标车)最少会与多少辆巡逻车相遇,请编程计算之。假设所有车辆到达关口的时刻都是整秒。
【输入格式】
输入文件第一行为两个用空格隔开的整数,分别为关口数n和巡逻车数m。(1<n<50,1<m<300)
接下来的m行每一行为一辆巡逻车的信息(按出发位置递增排序),格式为ni Ti ti,三项用空格隔开,分别表示第i辆巡逻车的出发位置、出发时刻和路上耗费的时间,其中ni和ti为整数,Ti形如hhmmss,表示时、分、秒,采用24小时制,不足两位的数用前置0补齐。(1<=ni<n,05:00:00<=Ti<=23:00:00,300<=ti<=600)
【输出格式】
输出文件第一行为目标车与巡逻车相遇次数。第二行为目标车与巡逻车相遇次数最少时最早到达第n个关口的时刻(格式同输入中的Ti)。
【样例输入】
3 2
1 060000 301
2 060300 600
【样例输出】
0
061301