Problem D
Bumper-To-Bumper Traffic
The road is modelled as the real line (units in meters). So a car is identified with its position on the line. Also, cars are $4.4$ meters long.
Given initial positions of two cars that are driving along the real line in the positive direction and a transcript of their speed changes, did these cars ever collide? While such a collision would be very slow speed (a “bumper tap”), any collision could result in erroneous readings from the black box in the future so the portions of the transcripts after a collision might not make sense.
Input
There is only one test case. The first line contains two integers $0 \leq X_1, X_2 \leq 10^6$ indicating the initial positions of the rears of the two vehicles in meters. You are guaranteed either $X_1 + 5 \leq X_2$ or $X_2 + 5 \leq X_1$. Initially (at time $0$), the two cars are stopped.
The second line begins with a number $0 \leq N_1 \leq 10^5$ indicating the number of times the speed of the first car changed. The rest of the line contains $N_1$ integers $0 < T_1 < T_2 < \ldots < T_{n_1} \leq 10^6$ indicating the times (in seconds) the first vehicle changed speeds. So at time $T_1$ it begins driving at $1$ m/s, at time $T_2$ it stops, at time $T_3$ it begins driving at $1$ m/s, and so on.
The last line begins with a number $0 \leq N_2 \leq 10^5$ and is followed by $N_2$ integers $0 < T’_1 < T’_2 < \ldots < T’_{n_2} \leq 10^6$ that describe the times the second vehicle starts and stops.
Output
If the vehicles collide, output the message bumper tap at time $S$ on a single line where $S$ is the number of seconds from time $0$ that the vehicles first collide, rounded up to the nearest second. If the vehicles do not collide, output the message safe and sound on a single line.
| Sample Input 1 | Sample Output 1 |
|---|---|
0 5 3 1 4 5 3 1 4 6 |
bumper tap at time 6 |
| Sample Input 2 | Sample Output 2 |
|---|---|
10 0 2 1 2 1 1 |
bumper tap at time 8 |
| Sample Input 3 | Sample Output 3 |
|---|---|
2 13 1 1 3 4 7 10 |
safe and sound |
