Числа сягають 10^{12}, тому перебирати їх усі неможливо. Це класична задача на динаміку за цифрами.
Спершу зведемо задачу до однієї межі. Позначимо — кількість чудових чисел у відрізку . Тоді відповідь дорівнює F(b) - F(a-1).
Тепер порахуємо . Запишемо як рядок цифр і будуватимемо число зліва направо, зберігаючи такий стан:
— скільки цифр уже поставлено;
— чи збігається побудований префікс з префіксом (якщо так, наступна цифра обмежена зверху відповідною цифрою , інакше — дев'яткою);
— чи почалося вже саме число (потрібно, щоб коректно обробити провідні нулі для коротших чисел);
— остання поставлена цифра.
Перехід: перебираємо наступну цифру від до межі. Якщо число вже почалося, вимагаємо d \ge \mathrm{prev} — саме це й означає неспадання. Якщо ще не почалося, то d = 0 залишає число «не початим», а d \ge 1 починає його.
База: дійшовши до кінця рядка, повертаємо , якщо число почалося, і інакше.
Стани мемоізуються, їх лише 13 \cdot 2 \cdot 2 \cdot 10, а переходів — по десять, тому обчислення миттєве.
Відповідь може бути великою, але не критично — усе одно рахуйте у 64-бітному типі, як і саму межу 10^{12}.