#P1499. [CTSC2000] 公路巡逻

    ID: 543 远端评测题 1000ms 125MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>动态规划dp枚举暴力WC/CTSC/集训队2000

[CTSC2000] 公路巡逻

题目描述

在一条没有分岔的高速公路上有 nn 个关口,相邻两个关口之间的距离都是 10km10\rm km 。所有车辆在这条高速公路上的最低速度为 60km/h60\rm km/h ,最高速度为 120km/h120\rm km/h,并且只能在关口处改变速度。

巡逻的方式是在某个时刻 TiT_{i} 从第 nin_{i} 个关口派出一辆巡逻车匀速驶抵第 ni+1n_{i+1} 个关口,路上耗费的时间为 tit_{i} 秒。

两辆车相遇是指它们之间发生超车或者两车同时到达某关口(同时出发不算相遇)。

巡逻部门想知道一辆于 66 点整从第 11 个关口出发去第 nn 个关口的车(称为目标车)最少会与多少辆巡逻车相遇,请编程计算之。假设所有车辆到达关口的时刻都是整秒。

输入格式

输入文件第一行为两个整数,分别为关口数 nn 和巡逻车数 mm

接下来的 mm 行每一行为一辆巡逻车的信息(按出发位置递增排序),格式为 nin_{i}TiT_{i}tit_{i},分别表示第 ii 辆巡逻车的出发位置、出发时刻和路上耗费的时间,其中 nin_{i}TiT_{i} 为整数, TiT_{i} 形如 HHMMSS,表示时、分、秒,采用 2424 小时制,不足两位的数用前置 00 补齐。

输出格式

输出文件第一行为目标车与巡逻车相遇次数。

第二行为目标车与巡逻车相遇次数最少时最早到达第 nn 个关口的时刻(格式同输入中的 TiT_{i} )。

3 2
1 060000 301
2 060300 600

0
061301

提示

1<n<501 < n < 501<m<3001 < m < 3001ni<n1 \leq n_{i} < n300i600300 \leq i \leq 600,所有的 TiT_i 不早于 05:0005:00,不晚于 23:0023:00

CTSC2000 第一试