## Problem A. As simple as it gets ≡

• problems
 Author: A. Klenin Time limit: 1 sec Input file: input.txt Memory limit: 64 Mb Output file: output.txt

### Statement

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.

### Input file format

Input file contains integer N.

### Output file format

Output file must contain integer X. If there is no integer simpler than N, output file must contain 0 (zero).

1 ≤ N ≤ 231 − 1

### Sample tests

No. Input file (input.txt) Output file (output.txt)
1
111
0
2
765437654
765377777

### Explanation

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 = n1 n2… nK and X = x1 x2… xM.

The definition of X < N gives us two cases:

1. M < K,
2. M = K and there exists some p such that x1 = n1, x2 = n2, …, xp − 1 = np − 1 and xp < np

In the first case the condition of maximum possible X leads us to M = K − 1 and x1 = x2 = …  = xK − 1 = 9.

In the second case the same condition allows us to conclude that all digits of X after the p-th one are equal (xp + 1 = xp + 2 = …  = xK). 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, xp = 0… np − 1, xp + 1 = 0… 9. This solution requires O(q2 × log 2 N) operations, where q is the number representation base (q = 10 in this problem).

0.078s 0.009s 13