Задача 112
Прыгучие числа

Если, читая число слева направо, ни одна цифра не превышает цифру справа от нее, то такое число называется возрастающим; например, 134468.

Таким же образом, если ни одна цифра не превышает цифру слева от нее, число называется убывающим; например, 66420.

Назовем положительное целое число, не являющееся ни убывающим, ни возрастающим, "прыгучим" числом; например, 155349.

Очевидно, не существует прыгучих чисел меньше ста, однако больше половины чисел до одной тысячи (525) являются прыгучими. Вообще, первое число, пропорция прыгучих чисел до которого достигает 50% - это 538.

Удивительно, но далее прыгучие числа становятся все более и более распространенными, и когда мы достигнем 21780, пропорция прыгучих чисел будет равна 90%.

Найдите наименьшее число, пропорция прыгучих чисел до которого составляет ровно 99%.

Оригинал
 
© Проект Эйлера | Translated problems from ProjectEuler.net