I Thought of a Number
Autumn Tournament (2011)
Submission name: think.cpp
Problem summary
Bobi chooses a number. He divides it by a and subtracts a, then repeats those same two operations on the result, obtaining b. Recover the original number.
Input
Two integers a and b.
Output
The original number.
Constraints
1 ≤ a, b ≤ 100.
Worked example
Original statement sample, translated without changing its numeric data.
Input
7 33
Output
2009
Solution analysis
- Work backward from the final result b. The inverse of subtracting a is adding a; the inverse of dividing by a is multiplying by a.
- Undo one full round with (value + a) × a, and apply that inverse twice. int is sufficient: the maximum answer is 2,010,000.
- For a = 7 and b = 33, the previous value is (33 + 7) × 7 = 280. The original value is (280 + 7) × 7 = 2009.
Why it works
For any value x, applying the forward round to (x + a)a yields ((x + a)a)/a − a = x. Thus each inverse round exactly undoes one forward round. Applying it twice recovers the original number.
Complexity: O(1) time and O(1) extra space: the input has a fixed number of values.
Watch out. Undo the operations in reverse order. The repeated action includes both division and subtraction.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
using namespace std;
int main(){
int a,b;
cin>>a>>b;
int value=b;
for(int round=0;round<2;round++){
// Undo subtraction first, then division.
value=(value+a)*a;
}
cout<<value<<'\n';
}