9BUnreviewed1200GPT-5.4 (high)

Running Student

Progressive hints first, then the full explanation and implementation when you're ready to cash out.

brute force geometry implementation

Original problem

Review status

AI-generated and still unreviewed. Double-check the details before internalizing them.

Hints

Progressive nudges

Open only as much as you need to keep the solve alive.

For any fixed stop $i$ , can you write the student's total travel time as two independent pieces: time on the bus and time running?

The bus starts at $(0,0)$ and moves only along the $x$ -axis with constant speed $v_b$ . So reaching stop $i$ at $(x_i,0)$ always takes exactly $\frac{x_i}{v_b}$ .

If he gets off at stop $i$ , he then runs straight to the university at $(x_u,y_u)$ . The running distance is

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

so the running time is $\frac{d_i}{v_s}$ .

Now there’s no hidden DP, no binary search, no black magic. For every stop $i$ from $2$ to $n$ , compute

T_i = \frac{x_i}{v_b} + \frac{\sqrt{(x_i-x_u)^2 + y_u^2}}{v_s}

and choose the stop with minimum $T_i$ .

The only gotcha is ties. If two stops have the same total time (compare with some tiny $\varepsilon$ ), pick the one closer to the university, i.e. the one with smaller $d_i$ . Since $n \le 100$ , a plain $O(n)$ scan is more than enough. Nice and brutally simple.

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:

stay on the bus until stop $i$ ,
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.

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

void setIO() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
}

int main() {
    setIO();

    int n;
    long double vb, vs;
    cin >> n >> vb >> vs;

    vector<ll> x(n + 1);
    for (int i = 1; i <= n; ++i) cin >> x[i];

    ll xu, yu;
    cin >> xu >> yu;

    const long double EPS = 1e-12L;

    int ans = 2;
    long double bestTime = 1e100L;
    long double bestDist = 1e100L;

    for (int i = 2; i <= n; ++i) {
        long double dx = (long double)x[i] - (long double)xu;
        long double dy = (long double)yu;
        long double dist = sqrtl(dx * dx + dy * dy);
        long double total = (long double)x[i] / vb + dist / vs;

        if (total + EPS < bestTime ||
            (fabsl(total - bestTime) <= EPS && dist + EPS < bestDist)) {
            bestTime = total;
            bestDist = dist;
            ans = i;
        }
    }

    cout << ans << '\n';
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

void setIO() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
}

int main() {
    setIO();

    int n;
    long double vb, vs;
    cin >> n >> vb >> vs;

    vector<ll> x(n + 1);
    for (int i = 1; i <= n; ++i) cin >> x[i];

    ll xu, yu;
    cin >> xu >> yu;

    const long double EPS = 1e-12L;

    int ans = 2;
    long double bestTime = 1e100L;
    long double bestDist = 1e100L;

    for (int i = 2; i <= n; ++i) {
        long double dx = (long double)x[i] - (long double)xu;
        long double dy = (long double)yu;
        long double dist = sqrtl(dx * dx + dy * dy);
        long double total = (long double)x[i] / vb + dist / vs;

        if (total + EPS < bestTime ||
            (fabsl(total - bestTime) <= EPS && dist + EPS < bestDist)) {
            bestTime = total;
            bestDist = dist;
            ans = i;
        }
    }

    cout << ans << '\n';
    return 0;
}

View on Codeforces Back to the list