GitBook

Digit Counting
Time Limit: 3000MS   Memory Limit: Unknown   64bit IO Format: %lld & %llu

Description

Download as PDF

Trung is bored with his mathematics homeworks. He takes a piece of chalk and starts writing a sequence of consecutive integers starting with 1 to N(1 < N < 10000) . After that, he counts the number of times each digit (0 to 9) appears in the sequence. For example, with N = 13 , the sequence is:

12345678910111213

In this sequence, 0 appears once, 1 appears 6 times, 2 appears 2 times, 3 appears 3 times, and each digit from 4 to 9 appears once. After playing for a while, Trung gets bored again. He now wants to write a program to do this for him. Your task is to help him with writing this program.

Input 

The input file consists of several data sets. The first line of the input file contains the number of data sets which is a positive integer and is not bigger than 20. The following lines describe the data sets.

For each test case, there is one single line containing the number N .

Output 

For each test case, write sequentially in one line the number of digit 0, 1,...9 separated by a space.

Sample Input 

2 
3 
13

Sample Output 

0 1 1 1 0 0 0 0 0 0 
1 6 2 2 1 1 1 1 1 1


/*用字符的形式保存整数

然后再判断就好了*/

刚开始想的是上面这种给一串数让找

结果发现是找 1~N 的所有数字出现的次数……

于是被坑了 -.-


所以就要考虑是否超时的问题……

然后还是感觉直接打表好了

毕竟这个问题如果超时的话应该就是重复了很多已经算过的运算

/*(而且给出的示例输出最后一个数字后有个空格~ xi xi xi)*/

好坑的题目啊 上面那括号里的一句不对

虽然题目示例输出有空格 但结果还是要求不带空格的-.-

如果最后有空格 会PE…… -.-


AC代码:

#include<stdio.h>
int a[10010][10];
int main() {
	int n,t;
//	int a[10010][10]; 放到这里在数据大的时候会WA
	for(int i=1; i<10010; i++) {
		for(int j=i; j; j/=10) {
			for(int k=i; k<10010; k++)
				a[k][j%10]++;
		}
	}
	scanf("%d",&n);
	while(n--) {
		scanf("%d",&t);
		for(int i=0; i<9; i++)
			printf("%d ",a[t][i]);
		printf("%d\n",a[t][9]);
	}
	return 0;
}


注意数组需要放在 int main 外面……

-.- 应该是所谓溢出的问题吧


再附一个根据别人写的来写的打表法

这个打表的时候的第三个循环用的不一样

(也就是记录上次数据的方法)


#include<stdio.h>
int a[10010][10];
int main() {
	int n,t;
	for(int i=1; i<10010; i++) {
		for(int j=i; j; j/=10) {
			a[i][j%10]++;
		}
		for(int j=0; j<10; j++)
			a[i][j]+=a[i-1][j];
	}
	scanf("%d",&n);
	while(n--) {
		scanf("%d",&t);
		for(int i=0; i<9; i++)
			printf("%d ",a[t][i]);
		printf("%d\n",a[t][9]);
	}
	return 0;
}



PS:

写AC代码的时候还意外写出了第一种理解的代码-.-

好吧~也留作纪念好了

#include<stdio.h>
int main() {
	int n,t;
	int a[10010][10];
	for(int i=1; i<10010; i++) {
		for(int j=i; j; j/=10) {
			a[i][j%10]++;
		}
	}
	scanf("%d",&n);
	while(n--) {
		scanf("%d",&t);
		for(int i=0; i<10; i++)
			printf("%d ",a[t][i]);
		printf("\n");
	}
	return 0;
}



题目地址:【UVa】[1225]Digit Counting