# 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;

}