P1499 [CTSC2000] Highway Patrol

On a straight highway with no forks, there are $n$ checkpoints, and the distance between any two adjacent checkpoints is $10\rm km$ . All vehicles on this highway have a minimum speed of $60\rm km/h$ and a maximum speed of $120\rm km/h$, and they may change speed only at checkpoints. Patrolling is performed as follows: at some time $T_{i}$, a patrol car is dispatched from checkpoint $n_{i}$, travels at a constant speed to checkpoint $n_{i}+1$, and spends $t_{i}$ seconds on the road. Two cars are considered to have met if one overtakes the other or if both arrive at the same checkpoint at the same time (departing at the same time does not count as a meeting). The patrol department wants to know the minimum number of patrol cars that a car (the “target car”) departing from checkpoint $1$ at exactly $6$ o’clock to checkpoint $n$ will meet. Please write a program to compute this. Assume that all vehicles arrive at checkpoints at integer seconds.

The first line of the input file contains two integers, the number of checkpoints $n$ and the number of patrol cars $m$. Each of the next $m$ lines describes one patrol car (sorted by increasing starting position). The format is $n_{i}$, $T_{i}$, $t_{i}$, representing the $i$-th patrol car’s starting position, departure time, and time spent on the road, respectively. Here $n_{i}$ and $T_{i}$ are integers. $T_{i}$ has the form `HHMMSS`, representing hour, minute, and second in 24-hour time; numbers with fewer than two digits are padded with a leading 0.

The first line of the output file is the number of meetings between the target car and the patrol cars. The second line is the earliest arrival time at checkpoint $n$ when the number of meetings is minimized (format is the same as $T_{i}$ in the input).

Constraints: $1 < n < 50$，$1 < m < 300$，$1 \leq n_{i} < n$，$300 \leq t_i \leq 600$，all $T_i$ are no earlier than 05:00 and no later than 23:00. CTSC 2000 First Session. Translated by ChatGPT 5