| Author: | Антон Карабанов | Time limit: | 1 sec | |
| Input file: | Standard input | Memory limit: | 256 Mb | |
| Output file: | Standard output |
Astrologer Timofey considers a year to be happy if different consecutive digits are used in its notation. For example, the nearest such year will occur in 2031. Determine, by the year number, how many years it will take for a happy year to come?
The input consists of a single line containing a natural number n — the year number.
Output a single non-negative integer — the answer to the problem.
1 ≤ n ≤ 9876543210
| No. | Standard input | Standard output |
|---|---|---|
| 1 | |
|
| 2 | |
|
Рассмотрим все перестановки цифр от 1 до длины числа n. Их ровно n!
С помощью бинарного поиска по номеру перестановки определим ту, которая строго больше n, но меньше всех остальных.
Нам понадобится алгоритм восстановления перестановки по её номеру.
Повторим такую же процедуру для перестановок цифр от 2 до длины числа n + 1, и так далее.
В итоге мы найдём нужную перестановку или определим, что для числа n нужной перестановки той же длины нет. Тогда она будет иметь вид 1023... и иметь длину на 1 больше длины числа n.