Separating Two Sets of Track Supporters
National Olympiad — National round (2014 season)
Submission name: supporters.cpp
Problem summary
Choose distinct proper divisor spacings 2≤d1<d2<L so regularly spaced opposing groups meet only at positions 0 and L. Under the released official judge interpretation, minimize d2−d1.
Source clarification. The printed prose asks for the closest numbers of groups and does not explicitly exclude spacing L. The official released test/solution package instead uses distinct proper spacings and minimizes |d1−d2|. This explanation and code follow that verified judge interpretation; these are genuine source ambiguities, not mathematical consequences of the printed wording.
Input
Track length L.
Output
The spacings in increasing order, or No solution.
Constraints
1 ≤ L ≤ 10^9. The printed prose and released judge differ; see the source clarification.
Worked example
Input and output for the worked example discussed below.
Input
12
Output
3 4
Solution analysis
- Both spacings divide L, because groups must be present at the finish. The first common positive group position is lcm(d1,d2), so no interior collision means lcm(d1,d2)=L.
- Enumerate all proper divisors at least 2 by checking factors through √L. Inspect every distinct pair and retain one with lcm L and the smallest spacing difference. Compute lcm as d1/gcd(d1,d2)×d2 in 64-bit.
- For L=12, spacings 3 and 4 meet first at 12 and differ by 1. Prime 13 has no candidate pair and gives No solution. The proper-divisor restriction and spacing objective follow the public released tests, not an unsupported interpretation of the contradictory prose.
Why it works
Divisor enumeration finds every permitted spacing. The lcm test is equivalent to no shared interior position. Checking every pair and minimizing the difference therefore gives the optimum under the explicitly stated released-judge interpretation.
Watch out. The prose’s group-count objective is different. Do not silently allow L as a spacing or invent another tie rule. Use long long for lcm products.
Commented C++17 solution
An independently written complete program with standard headers.
#include<algorithm>
#include<iostream>
#include<numeric>
#include<vector>
using namespace std;
int main(){
long long length;
cin>>length;
vector<long long>divisors;
for(long long d=2;d*d<=length;d++){
if(length%d==0){
divisors.push_back(d);
if(d*d!=length){
divisors.push_back(length/d);
}
}
}
sort(divisors.begin(),divisors.end());
long long difference=length;
long long bestFirst=0;
long long bestSecond=0;
for(size_t i=0;i<divisors.size();i++){
for(size_t j=i+1;j<divisors.size();j++){
long long a=divisors[i];
long long b=divisors[j];
// The first common positive position must be the finish itself.
if(a/gcd(a,b)*b==length&&b-a<difference){
difference=b-a;
bestFirst=a;
bestSecond=b;
}
}
}
if(bestFirst==0){
cout<<"No solution\n";
}
else{
cout<<bestFirst<<' '<<bestSecond<<'\n';
}
}