The Tile Ledger
National Olympiad — National round (2009 season)
Submission name: pool.cpp
Problem summary
After each newly tiled row on one of four walls, a ledger records the accumulated row counts on all four walls. An accountant sums every number in the ledger and obtains S. Recover the actual number of rows tiled.
Input
A single integer S, guaranteed to arise from such a ledger.
Output
The actual number of tiled rows.
Constraints
1 ≤ S < 1,000,000,000.
Worked example
An independently prepared example for this explanation.
Input
15
Output
5
Solution analysis
- After the first operation the four counts sum to 1; after the second they sum to 2, and after operation r they sum to r. The choice of wall never changes these totals.
- Therefore a ledger for r rows has sum 1 + 2 + … + r. Starting from zero, add successive integers until the running sum reaches S.
- For S = 15 the partial sums are 1, 3, 6, 10, 15. Five additions reach the target, so five rows were tiled.
Why it works
Every operation increases exactly one wall count by 1, so the sum of counts in ledger entry i is i. Thus S is the r-th triangular number. The loop produces these triangular numbers in strictly increasing order and stops at the unique matching r.
Watch out. The answer does not depend on which wall was tiled. Use 64-bit counters for the accumulated sum.
Commented C++17 solution
An independently written complete program with standard headers.
#include <iostream>
using namespace std;
int main() {
long long target;
cin >> target;
long long sum = 0;
long long rows = 0;
// The i-th ledger entry sums to i, independent of the chosen wall.
while (sum < target) {
rows++;
sum += rows;
}
cout << rows << '\n';
}