Evenly Spaced Chestnuts
National Olympiad — National round (2013 season)
Submission name: chestnut.cpp
Problem summary
Existing trees stand in a line with given adjacent gaps. Add the fewest trees between them so every final adjacent gap is equal.
Input
n, then n−1 adjacent distances in order.
Output
The minimum number of new trees.
Constraints
1 ≤ n ≤ 1000; 1 ≤ each gap < 1,000,000,000; the given gaps are distinct.
Worked example
An independently prepared example for this explanation.
Input
4 63 18 54
Output
12
Solution analysis
- Any final spacing must divide every original gap. The largest possible spacing is therefore the gcd of all gaps.
- A gap x divided into spacing g needs x/g−1 new trees. Add these quantities, or compute totalGap/g−(n−1). A single existing tree needs no additions.
- For gaps 63,18,54 the gcd is 9. The new-tree counts are 6,1,5, totaling 12.
Why it works
The final spacing divides each original gap, so it cannot exceed their gcd. Choosing the gcd is feasible and uses the fewest subdivisions in every gap. Summing one fewer than each number of subdivisions counts exactly the inserted trees.
Watch out. With n=1 there are no gaps and the answer is zero. Use long long for the total distance.
Commented C++17 solution
An independently written complete program with standard headers.
#include <iostream>
#include <numeric>
using namespace std;
int main() {
int n;
cin >> n;
long long spacing = 0;
long long total = 0;
for (int i = 1; i < n; i++) {
long long gap;
cin >> gap;
spacing = gcd(spacing, gap);
total += gap;
}
if (n == 1) {
cout << 0 << '\n';
} else {
// Each old gap contributes gap/gcd - 1 new trees.
cout << total / spacing - (n - 1) << '\n';
}
}