给定一个十进制正整数N，写下从1开始，到N的所有正数，计算出其中出现所有1的个数。

 

例如：n = 12，包含了5个1。1,10,12共包含3个1，11包含2个1，总共5个1。

Input

输入N(1 <= N <= 10^9)

Output

输出包含1的个数

Input示例

12

Output示例

5

注意数据规模，只好找规律了。

代码实现：

1 #include
        
          2 int n,a=1,ans; 3 int main(){ 4     scanf("%d",&n); 5     while(n>=a){ 6         ans+=n/(10*a)*a; 7         if(n/a%10>1) ans+=a; 8         if(n/a%10==1) ans+=n%a+1; 9         a*=10;10     }11     printf("%d\n",ans);12     return 0;13 }
        

有人说是数位DP什么的。

题目来源：51Nod