「SuperOJ 225」计算数字

计算数字

题目描述

当连续写下从十进制整数 1 开始到某个整数 N 之间的所有整数时,能得到如下的数字序列:
12345678910111213141516171819202122 \cdots \cdots
编写一个程序,计算这个序列中的数字个数。

输入格式

输入的第一行且是唯一的一行包含:一个整数 N,1 \leq N \leq 100,000,000。

输出格式

输出的第一行且是唯一的一行应包含:由给定的整数所产生的序列的数字个数。

样例数据 1

输入

1
15

输出

1
21

分析

直接暴力肯定会TLE,数学方法递推。

源码

1
2
3
4
5
6
7
8
9
10
11
#include <bits/stdc++.h>
using namespace std;
int n, t = 1, p, ans;
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cin >> n;
for (; n / t; t = (t << 1) + (t << 3)) ans += ((t << 3) + t) * ++p;
cout << ans - (t - n - 1) * p;
return 0;
}
#

Comments

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×