The Devil’s Bridge
National Olympiad — National round (2010 season)
Submission name: deadbeat.cpp
Problem summary
A person starts with a leva. Each bridge crossing doubles the money, then requires paying n leva. Determine whether the money grows forever (1), stays constant (2), becomes exactly zero (3), or eventually cannot cover the fee (4). For case 2 also print the constant amount; for case 4 print the unpaid part of that fee. Print 0 only if none applies.
Input
Two positive integers a and n.
Output
The case number; additionally the constant amount for case 2 or debt for case 4, separated by a space.
Constraints
1 ≤ a, n ≤ 1000.
Worked example
An independently prepared example for this explanation.
Input
13 15
Output
4 1
Solution analysis
- One successful crossing changes x into 2x − n. If x > n, the increase x − n is positive and grows afterward, so this is case 1. If x = n, the amount stays n forever: case 2.
- When x < n the amount decreases after each paid crossing. Repeatedly compute 2x − n until it is zero or negative. Zero is case 3; a negative result means the doubled money was short by its absolute value, giving case 4.
- For a = 13 and n = 15, the amounts after fees are 11, 7, then −1. On the third crossing there are only 14 leva for a 15-leva fee, so the output is 4 1.
Why it works
The comparison with n characterizes the recurrence’s growth and fixed point. For 0 < x < n, the positive gap n − x doubles after each update, so the process reaches a nonpositive result in finitely many steps. The first such result distinguishes exact payment from a shortfall and gives the debt exactly. Thus every positive input belongs to one of the four cases.
Watch out. Double before paying. In case 4 print only the unpaid portion, not the entire fee. There is no need to simulate unbounded growth.
Commented C++17 solution
An independently written complete program with standard headers.
#include <iostream>
using namespace std;
int main() {
int money, fee;
cin >> money >> fee;
if (money > fee) {
cout << "1\n";
} else if (money == fee) {
cout << "2 " << money << '\n';
} else {
// Below the fixed point fee, every paid crossing reduces the money.
while (money > 0) {
money = 2 * money - fee;
}
if (money == 0) {
cout << "3\n";
} else {
cout << "4 " << -money << '\n';
}
}
}