Задача: Эскалатор
В Баку вскоре откроется новая станция метро. Эскалатор в метро состоит из n ступенек, пронумерованных целыми числами от $1$ до $n$. На ступеньках с номерами, кратными десяти, а также на первой и последней ступеньке, пишут их номера. При записи номера на каждую записанную цифру уходит одно и то же количество краски.
Чтобы рассчитать необходимое количество краски, требуется узнать, сколько цифр будет написано. Напишите программу, которая определяет, сколько всего цифр будет использовано в номерах подписанных ступенек.
Входные данные
Одно целое число $n\;\left(1 \leq n \leq 10^{18}\right)$ — количество ступеней эскалатора.
Выходные данные
Выведите суммарное количество цифр в номерах подписанных ступенек.
Тесты
| Ввод | Вывод |
|---|---|
| 1000000000000000000 | 1788888888888888908 |
| 242 | 67 |
| 250 | 67 |
| 999 | 292 |
| 1000 | 293 |
| 1 | 1 |
| 2 | 2 |
Решение
Идея решения заключается в том чтобы искать количество помеченных ступенек на отрезках $10-99,100-999,\ldots,10^{x}-\left(10^{x+1}-1\right).$ Легко понять что помеченных ступенек $9\cdot 10^{x}.$ Это суть метода, а остальное это реализация, которую я покажу в программе.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
#include <iostream> using namespace std; #define ll long long int main() { ll n, q = 0, s = 1/*учитываем первую ступеньку*/, d = 0, d1 = 0; cin >> n; if (n == 1){cout << 1;return 0;} //важный частный случай,где первая ступенька последняя bool n1 = (n % 10 != 0); //что бы не забыть про последнюю ступеньку ll n2 = n / 10; //кол-во помеченных ступенек без учета первой и последней while (n > 9) { n /= 10; q++;//с каждым десятком кол-во цифр в числе растет s += (d - d1) * q;//реализация указанной выше идеи d1 = d; d = d * 10 + 9;//числа, которые я уже учел } n2 -= (d) / 10;//помеченные не учтеные ступеньки q++; s += n2 * q; s += n1 * q;//считаем последнюю ступеньку cout << s; return 0; } |