Nearest Charging Station
Autumn Tournament (2023)
Submission name: bike.cpp
Problem summary
A circular bicycle path has length N. A cyclist is at coordinate P and three distinct charging stations have coordinates measured from the same origin in the same direction. The cyclist is not at a station and may travel in either direction. Find the distance to the nearest station.
Input
N and P on the first line; three station coordinates on the second.
Output
The shortest distance to any station.
Constraints
5 ≤ N ≤ 10^12; 0 ≤ P < N; each station coordinate is in [0,N−1].
Worked example
The example is reproduced from the original tournament statement.
Input
10 3 4 7 8
Output
1
Solution analysis
- For a station at coordinate q, the difference d=|P−q| measures one of the two arcs joining the positions. The other arc has length N−d.
- Its shortest distance is min(d,N−d). Compute this for all three stations and retain the smallest value. Coordinates up to 10^12 require long long.
- For N=10 and P=3, stations 4,7,8 have shortest distances 1,4,5. The answer is 1. A station near coordinate N can also be close to a cyclist near zero.
Why it works
The two arcs partition the circular path and have lengths d and N−d. Any shortest route to that station follows the shorter arc. Minimizing these exact distances over all stations therefore gives the nearest reachable station.
Watch out. Do not use only absolute difference: travel can cross the origin. Use 64-bit integers.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: The two arcs partition the circular path and have lengths d and N−d. Any shortest route to
// that station follows the shorter arc.
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
long long n,p;
cin>>n>>p;
long long answer=n;
for(int i=0;i<3;i++){
long long q;
cin>>q;
long long difference=q>p?q-p:p-q;
answer=min(answer,min(difference,n-difference));
}
cout<<answer<<'\n';
}