Thứ Hai, 25 tháng 11, 2013

Đế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:
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ệ.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#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;
}