CHEF N TIMINGS - APOC2_02 - EDITORIAL
PROBLEM LINK
Author: codechefsrm
Editorialist : codechefsrm
DIFFICULTY
MEDIUM
PREREQUISITES
Basic programming
PROBLEM
Given a integer we have to output each test case in a new line which is largest nice integer smaller or equal to the given integer.
EXPLANATION
If we know how to check if the number is in
non-decreasing order and we are working with
then it is a easy question. You will take the
number, test if it is in non-decreasing order.
If not, decrease it by 1 and repeat the process
until the number is in non-decreasing order.
What is the problem here? If you get a big
number, this process will take too long time
( and you have to use proper variable type that
can handle big numbers, of course ). So how to
optimize it?
Decreasing the number
Let’s take the number 132 from the sample input. It’s clearly not in non-decreasing order. If you would follow the steps above, you decrease it by 1 and get 131, then 130 and finally 129 which is nice. It would be better to extract the last number ( because it violates the order ), decrease the whole number by the last number + 1 and chek again, if it is in the right order. What about the other numbers? Well, if you don’t want to search for another numbers that violates the order and I don’t know what else, you can do this :
take 10 as subtrahend
is the number in non-decreasing order?
if yes, return the number, if no, continue
if the number ends with 99
( i. e. subtrahend * 10 – 1 ),
multiply subtrahend by 10
substract the subtrahend from the number
go to step 2
By how much did we improve the algorithm now?
Using the first algorithm, it would take more
than 1016 rounds to get the right result. After
this optimization, it takes only 16 rounds!
SOLUTION :
Setter's Solution
#include <bits/stdc++.h>
using namespace std;
bool isNonDecreasing(unsigned long long number) {
int remainder = 10;
while( number > 0 ) {
if( number % 10 <= remainder ) {
remainder = number % 10;
number /= 10;
} else {
return false;
}
}
return true;
}
unsigned long long lastTidyNumber(unsigned long long number) {
unsigned long long subtrahend = ( number % 10 ) + 1;
number -= subtrahend;
subtrahend = 10;
while( !isNonDecreasing(number) ) {
if( number % (subtrahend * 10) == (subtrahend * 10) - 1 ) {
subtrahend *= 10;
}
number -= subtrahend;
}
return number;
}
int main() {
int t; cin >> t;
unsigned long long n;
for( int i = 0; i < t; i++ ) {
cin >> n;
if( isNonDecreasing(n) ) {
cout << n << “\n”;
}
else {
cout << lastTidyNumber(n) << “\n”;
}
}
return 0;
}