Problem B
Bumper-To-Bumper Traffic

Photo by mckay savage cc by-sa 2.0
It’s the slow crawl of rush hour. At any point of time, each vehicle is either stopped or is moving at the extremely slow speed of $1$ meter per second. Lately, vehicles come equipped with a simple “black box” that record all changes in a vehicle’s speed. In this problem, speeds change instantaneously.

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.


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.


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

Please log in to submit a solution to this problem

Log in