Half a Competitor More
National Olympiad — National round (2010 season)
Submission name: halfman.cpp
Problem summary
After each of N stages, half the competitors in that stage plus half a competitor are eliminated. One winner remains after the last stage. Find the starting number of competitors.
Input
An integer N.
Output
The original number of competitors.
Constraints
1 < N < 54.
Worked example
An independently prepared example for this explanation.
Input
3
Output
15
Solution analysis
- If x competitors remain after a stage, and y entered it, then x = y − (y/2 + 1/2) = (y − 1)/2.
- Reverse this relationship: y = 2x + 1. Start with one winner and apply that update N times.
- For three stages, reverse counts are 1 → 3 → 7 → 15. Indeed 15 leaves 7, then 3, then 1.
Why it works
The reverse equation y = 2x + 1 uniquely reconstructs the previous stage’s integer count. Starting with the single winner, each iteration therefore recovers one earlier stage. After N iterations it recovers the initial count.
Watch out. Use an integer reverse recurrence rather than floating point halves. The maximum result is 2^54 − 1, which needs 64-bit storage.
Commented C++17 solution
An independently written complete program with standard headers.
#include <iostream>
using namespace std;
int main() {
int stages;
cin >> stages;
long long competitors = 1;
for (int stage = 0; stage < stages; stage++) {
// Reverse remaining = (previous - 1) / 2.
competitors = 2 * competitors + 1;
}
cout << competitors << '\n';
}