Ввести натуральное число S⩽10¹⁸. Найти такие два минимально возможных целых неотрицательных числа L и R, что в последовательности подряд идущих чисел {L L+1 … R-1 R} содержится ровно S цифр (с учётом повторений), а длина последовательности (W) максимальна. Вывести W, L и R.
11
Подсказка: ∃ чуть ли не формула для этой последовательности, но она какая-то сложная. Проще вчерне подобрать приблизительные значения, а на более тщательный подбор есть целая секунда.
10 1 10
Сама последовательность — {1 2 3 4 5 6 7 8 9 10}
Спойлер:
Количество n-значных неотрицательных целых чисел: Nn = 10n - Nn-1; где N1=10. Цифр в них ровно в n раз больше ☺
Вычислим такое R, что количество цифр S0R в последовательности (L=0)…R не больше S, а количество цифр S0R+1 в последовательности (L=0)…R+1 — больше S
До тех пор, пока SLR не равно S
Если SLR > S, увеличим L
Если SLR < S, увеличим R