Recover the Numbers
Autumn Tournament (2023)
Submission name: numbers.cpp
Problem summary
Two three-digit numbers a and b end in zero and have middle digit zero, respectively. Deleting those zeros gives equal two-digit numbers x and y. Choose a and b so that x+y is as large as possible but strictly less than S.
Input
One integer S.
Output
Print x+y, a and b separated by spaces. If impossible, print 0 0 0.
Constraints
0 < S < 1000; S is an integer.
Worked example
The example is reproduced from the original tournament statement.
Input
33
Output
32 160 106
Solution analysis
- Write x=y=t. Since both resulting numbers have two digits, 10 ≤ t ≤ 99. The required sum is 2t.
- The greatest integer satisfying 2t<S is floor((S−1)/2). Cap it at 99; if it is below 10, no valid pair exists. Reinsert the deleted zeros: a=10t and b=100 floor(t/10)+(t mod 10).
- For S=33, t=16 gives sum 32. The original numbers are 160 and 106. For S=10, even the smallest sum 20 is too large.
Why it works
Every valid solution corresponds to a t between 10 and 99 with 2t<S. Taking the largest such t maximizes 2t. Reinserting the zeros produces the unique original numbers and preserves their three-digit lengths. If t<10, no allowed value exists.
Watch out. The inequality is strict. Values above 99 cannot be used even when S is large.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
int s;
cin>>s;
int t=min(99,(s-1)/2);
if(t<10){
cout<<"0 0 0\n";
return 0;
}
// Reinsert the zero at the end and in the middle.
int a=t*10;
int b=(t/10)*100+t%10;
cout<<2*t<<' '<<a<<' '<<b<<'\n';
}