01/10/2018, 21:38

[Spoj] Đếm số chữ số 0,1,2,3,…,9 trong dãy số từ 1->n | MDIGITS

[Spoj] Đếm số chữ số 0,1,2,3,…,9 trong dãy số từ 1->n | MDIGITS Tháng Sáu 11, 2013 nguyenvanquan7826 TT Spoj Leave a response Đề bài: http://vn.spoj.com/problems/MDIGITS/ Cho hai số nguyên a, b. Viết tất cả các ...

[Spoj] Đếm số chữ số 0,1,2,3,…,9 trong dãy số từ 1->n | MDIGITS

Đề bài: http://vn.spoj.com/problems/MDIGITS/
Cho hai số nguyên a, b. Viết tất cả các số nằm giữa a, b; tính cả 2 số này.
Tính xem mỗi chữ số 0, 1, .., 9 mỗi số xuất hiện bao nhiêu lần.
Ví dụ, nếu a = 1024 và b = 1032, dãy sẽ là
1024 1025 1026 1027 1028 1029 1030 1031 1032
và có 10 số 0, 10 số 1, 7 số 2, …

Ta đếm các chữ số từ 0->a, 0->b sau đó lấy lần lượt số chữ số của từng số (0->9) của b trừ đi của a.
Giải sử xét số 31627 (so với số 0), Ta xếp lần lượt các số như sau:
so

Ta xét các số ở cột đầu tiên, các số 0,1,2 có 10^4 số, số 3 sẽ có 1627+1 = 1628 số (ở hình trên khoanh số 0 chưa hết, chúng ta khoanh xuống tận số cuối cùng 00000)
Lại thấy từ cột 2 trở đi (xem hình) ta có thể chia thành các cụm (3 cụm) mà mỗi cụm gồm các sô 0->9 đều có 4*10^3 số.
Như vậy giờ ta chỉ việc xét tương tự đối với số 1627 mà thôi !
Khi đã đếm xong ta chú ý trừ đi các số 0 không hợp lệ (001) thì 2 số 0 ở đầu không hợp lệ.

#include <stdio.h>
#include <math.h>

int A[] = {1,10,100,1000,10000,100000,1000000,10000000,100000000};

void pro(int num, int len, int count[])
{
	int n, i;
	n = num / A[len];
	if (num ==0) 
	{
		count[n] += len+1;
		return;
	}
	for(i=0;i<n;i++)
		count[i] += A[len];
	count[n] += num % A[len] + 1;
	if(len==0) return;
	for(i=0;i<10;i++)
		count[i] += n*len*A[len-1];
	pro(num % A[len], len-1, count);
}

int main()
{
	int p1, p2, a, b, c, i;
	while(scanf("%d%d",&a,&b)==2 && a+b)
	{
		if(a>b)
		{
			c = a;
			a = b;
			b = c;
		}
		a--;
		int count1[10] = {1};
		int count2[10] = {1};
		if(a)
		{
			p1 = (int)floor(log10(a));
			pro(a, p1, count1);
			for(i=0; i<=p1; i++);
				count1[0] -= A[i];
		}

		p2 = (int)floor(log10(b));
		pro(b, p2, count2);

		for(i=0; i<=p2; i++)
			count2[0] -= A[i];

		printf("%d",count2[0]-count1[0]);
		for(i=1; i<10; i++) 
			printf(" %d",count2[i]-count1[i]);
		printf("n");
	}
	return 0;
}
0