Задача 112: Надувные номера
Работая слева направо, если цифра не превышена цифрой слева от нее, она называется все увеличивающимся числом; например, 134468. Аналогично, если цифра не будет превышена цифрой справа, она называется уменьшающимся числом; например, 66420. Мы будем называть положительное целое число, которое не увеличивает и не уменьшает «бодрящее» число; например, 155349. Очевидно, что не может быть никаких надувных чисел ниже ста, но чуть более половины чисел ниже одной тысячи (525) являются упругими. Фактически, наименьшее число, для которого доля бодрящих чисел вначале достигает 50%, составляет 538. Удивительно, что набирающие обороты цифры становятся все более распространенными, и к тому времени, когда мы достигнем 21780, доля надувных чисел равна 90%. Найдите наименьшее число, для которого доля надувных чисел составляет ровно 99%.