A Sum with Gentle Steps
National Olympiad — National round (2017 season)
Submission name: sum.cpp
Problem summary
Write n as a sum of at least two positive terms. The first and last terms must equal 1, and adjacent terms may differ by at most 1. Find the minimum possible number of terms.
Input
One integer n.
Output
The minimum number of terms.
Constraints
2 ≤ n ≤ 1000000000.
Worked example
An independently prepared example for this explanation.
Input
7
Output
5
Solution analysis
- With k positions, position i can be at most min(i,k+1−i), because the sequence must rise from 1 and return to 1 with steps of at most one. The maximum sum is therefore a symmetric mountain.
- If k = 2r−1, its maximum sum is r²; if k = 2r, it is r(r+1). Every sum between k and this maximum is attainable: start from the mountain and lower an internal maximum by one repeatedly until every term is 1.
- Binary-search the smallest k whose maximum reaches n. Search only 2 through n, so k ≤ n is automatic. For n = 7, four terms have maximum 6, while five have maximum 9; a valid five-term sum is 1+2+2+1+1.
Why it works
Each term is bounded by its distance from the two fixed endpoints, so the mountain gives an upper bound achieved by a valid sequence. While a term exceeds 1, lowering an internal global maximum by one preserves all adjacent differences and the endpoints. This produces every integer sum down to k. Hence k terms work exactly when k ≤ n ≤ maximum(k); the monotone maximum lets binary search find the smallest feasible k.
Watch out. A bound on the sum is sufficient only with an attainability argument. Use long long for the mountain product.
Commented C++17 solution
An independently written complete program with standard headers.
#include <algorithm>
#include <array>
#include <iostream>
#include <numeric>
#include <string>
#include <vector>
using namespace std;
long long maximumSum(long long terms) {
long long left = (terms + 1) / 2;
long long right = (terms + 2) / 2;
// Odd lengths give a square peak sum; even lengths give r*(r+1).
return left * right;
}
int main() {
long long n;
cin >> n;
long long low = 2;
long long high = n;
while (low < high) {
long long middle = low + (high - low) / 2;
if (maximumSum(middle) >= n) {
high = middle;
} else {
low = middle + 1;
}
}
cout << low << '\n';
}