Сколько цифр в нумерации страниц

В школьной библиотеке решили пронумеровать страницы в новом сборнике задач: на первой странице написали «1», на второй — «2» и так далее до страницы N.

Завхоз попросил понять, сколько всего цифр уйдёт на такую нумерацию (то есть суммарная длина всех записанных номеров страниц).

Важно: N может быть очень большим, так что ответ может не помещаться в 32-битный тип (как на олимпиадах). В Python это не проблема.

Формат ввода

Одно целое число N.

Формат вывода

Выведите одно целое число — сколько цифр будет написано в номерах страниц от 1 до N включительно.

Ограничения

• 1 ≤ N ≤ 1_000_000_000
• время: 1 c, память: 256 МБ

Пример

Ввод:

13

Вывод:

17

Пояснение: номера 1…9 дают 9 цифр, а 10…13 дают ещё 8 цифр (четыре двузначных номера). Итого 17.

Ключевое наблюдение: номера страниц с одинаковым количеством цифр образуют непрерывный блок, и каждый номер в блоке даёт одинаковый вклад в ответ.

Например, все двузначные номера (10…99) дают по 2 цифры каждый, значит их вклад равен кол-во_чисел * 2. То же самое для 1-значных, 3-значных и т.д. Поэтому вместо перебора 1…N (слишком долго) можно пройтись по блокам разрядов.

План:

• Заведи start = 1 — начало текущего блока (1, 10, 100, …) и digits = 1 — сколько цифр в числах этого блока.
• Пока start <= N:
• Конец блока для этого разряда: end = min(N, start*10 - 1).
• Сколько чисел в блоке: count = end - start + 1.
• Добавь в ответ count * digits.
• Перейди к следующему разряду: start *= 10, digits += 1.

Время: O(log10 N), потому что блоков максимум 10 (для N до 1e9). Память: O(1).

Частая ошибка: забыть ограничить последний блок числом N (использовать 99/999/… как конец всегда) или перепутать границы, потеряв +1 в end - start + 1.