Author:  A. Klenin  Time limit:  1 sec  
Input file:  input.txt  Memory limit:  64 Mb  
Output file:  output.txt 
Let us define that a positive integer A is simpler than a positive integer B if the decimal representation of A requires less different digits than the decimal representation of B.
For example, number 55 is simpler than 12 which in turn is simpler than 123.
Your program will be given a number N and must find the largest integer X such that X < N and X is simpler than N.
1 ≤ N ≤ 2^{31} − 1
No.  Input file (input.txt ) 
Output file (output.txt ) 

1 


2 


Obvious solution is to decrement the number until a simpler one is obtained. This solution may require O(N × log N) operations which is too slow.
To improve that, we need to work with decimal representations N = n_{1} n_{2}… n_{K} and X = x_{1} x_{2}… x_{M}.
The definition of X < N gives us two cases:
In the first case the condition of maximum possible X leads us to M = K − 1 and x_{1} = x_{2} = … = x_{K − 1} = 9.
In the second case the same condition allows us to conclude that all digits of X after the pth one are equal (x_{p + 1} = x_{p + 2} = … = x_{K}). Indeed, if for some X these are different, we can replace them all with the largest of them to obtain X′ > X. The X′ will be as simple or simpler than X and still less than N.
Thus, all possible values of X can be searched by checking all combinations of p = 1… N, x_{p} = 0… n_{p} − 1, x_{p + 1} = 0… 9. This solution requires O(q^{2} × log ^{2} N) operations, where q is the number representation base (q = 10 in this problem).