A1049. Counting Ones

The task is simple: given any positive integer N, you are supposed to count the total number of 1's in the decimal form of the integers from 1 to N. For example, given N being 12, there are five 1's in 1, 10, 11, and 12.

Input Specification:

Each input file contains one test case which gives the positive N (<=230).

Output Specification:

For each test case, print the number of 1's in one line.

Sample Input:

12

Sample Output:

5
 #include<cstdio>
#include<iostream>
using namespace std;
int main(){
long long N, a = , ans = , left, mid, right;
scanf("%lld", &N);
while(N / (a / ) != ){
left = N / a;
mid = N % a / (a / );
right = N % (a / );
if(mid == )
ans += left * (a / );
else if(mid == )
ans += left * (a / ) + right + ;
else if(mid > )
ans += (left + ) * (a / );
a *= ;
}
printf("%d", ans);
cin >> N;
return ;
}

总结:

1、本题应寻找规律完成。对于数字abcde来说,讨论第c位为1的有多少个数字,分为左边:ab,中间c, 右边de。当c = 1时,ab可以取0到ab的任意数字,当取0到ab - 1时,de位任意取。当ab取ab时,de位只能从0 到 de, 故共有ab * 1000 + de + 1个。  当c = 0时,为了让c能 =  1, ab位只能取0 到 ab - 1共ab种可能,de位任取,故共有ab*1000种可能。  当c > 1时,ab位可以取0到ab共ab+1种可能,de任取,故共有 (ab + 1)* 1000种可能。

上一篇:使用express创建web服务器


下一篇:python实现二叉树和它的七种遍历