Running Student

Observation 1

This is one of those problems where the hardest part is resisting the urge to invent something fancier than necessary. Don't. The problem is basically one formula per stop.

If the student gets off at stop $i$ (and note that $i=1$ is forbidden), then his total arrival time is

$$T_i = \underbrace{\frac{x_i}{v_b}}_{\text{time spent on the bus}} + \underbrace{\frac{\sqrt{(x_i-x_u)^2 + y_u^2}}{v_s}}_{\text{time spent running}}.$$

Why?

• The bus starts at $(0,0)$.
• It moves along the $x$-axis at constant speed $v_b$.
• So reaching stop $(x_i,0)$ takes exactly $\frac{x_i}{v_b}$.
• From there, the student runs in a straight line to $(x_u,y_u)$, whose distance is $$d_i = \sqrt{(x_i-x_u)^2 + y_u^2}.$$ Running at speed $v_s$ takes $\frac{d_i}{v_s}$.

That's the whole model. No transitions, no state, no drama.

Observation 2

We only have $n \le 100$ stops. That is tiny. So just try every valid stop:

$$i = 2,3,\dots,n.$$

For each stop, compute $T_i$ and keep the best one.

Tie-breaking

The statement says: if several stops give the same earliest arrival time, choose the stop closest to the university.

That means among equal-time candidates, minimize

$$d_i = \sqrt{(x_i-x_u)^2 + y_u^2}.$$

So the comparison rule is:

• if $T_i < T_{best}$, take stop $i$;
• if $T_i = T_{best}$, take the one with smaller $d_i$.

Because we are using floating-point arithmetic, compare times with a small epsilon, e.g.

$$\varepsilon = 10^{-12}.$$

Using long double is perfectly safe here.

Correctness sketch

For every allowed stop $i$, the student's route is uniquely determined:

1. stay on the bus until stop $i$,
2. run straight from $(x_i,0)$ to $(x_u,y_u)$.

The formula for $T_i$ computes exactly the total time of that route. Since the student must get off at some stop from $2$ to $n$, the optimal answer is simply the stop with minimum $T_i$. If several stops share that minimum, the statement explicitly tells us to choose the one with minimum distance to the university. Scanning all candidates and applying these rules therefore returns the correct stop.

No tricks. Just geometry plus implementation that doesn't screw up floating-point ties.

Complexity

We evaluate one formula per stop.

• Time: $O(n)$
• Memory: $O(1)$ extra

With $n \le 100$, this is hilariously cheap.