Editorial for Counting Digits


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

Code mẫu của flashmt

var a,b,i:longint;
    d,c:array[0..9] of longint;
    z:array[1..8] of longint;

procedure calc(m,n,k:longint);
var p,q,t,u,j,l:longint; s:string;
begin
     if m=n then
     begin
          str(n,s);
          for j:=1 to length(s) do
              inc(d[ord(s[j])-48]);
          exit;
     end;
     if k=0 then
     begin
          for j:=m to n do
          begin
               str(j,s);
               for t:=1 to length(s) do
                   inc(d[ord(s[t])-48]);
          end;
          exit;
     end;
     if m mod c[k] = 0 then p:=m
     else p:=m+c[k]-m mod c[k];
     inc(n);
     q:=n-n mod c[k];
     dec(n);
     if p>=q then calc(m,n,k-1)
     else
     begin
          t:=p div c[k];
          u:=q div c[k];
          for j:=0 to 9 do
              d[j]:=d[j]+c[k-1]*k*(u-t);
          for j:=t to u-1 do
          begin
               str(j,s);
               for l:=1 to length(s) do
                   inc(d[ord(s[l])-48],c[k]);
          end;
          if m<p then calc(m,p-1,k-1);
          if q<n+1 then calc(q,n,k-1);
     end;
end;

begin
     c[0]:=1;
     fillchar(d,sizeof(d),0);
     for i:=1 to 8 do c[i]:=c[i-1]*10;
     z[1]:=9;
     for i:=2 to 8 do z[i]:=z[i-1]*10;
     repeat
           readln(a,b);
           if (a+b=0) then break;
           if a>b then
           begin
                a:=a+b;
                b:=a-b;
                a:=a-b;
           end;
           fillchar(d,sizeof(d),0);
           calc(a,b,7);
           for i:=0 to 9 do write(d[i],' ');
           writeln;
     until false;
end.

Code mẫu của happyboy99x

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;

int p10[10];

struct Result {
    int a[10];

    Result(const int &v = 0, const int &n = 10) {
        memset(a, 0, sizeof a);
        for(int i = 0; i < n; ++i)
            a[i] = v;
    }

    Result operator * (const int &x) const {
        Result res = *this;
        for(int i = 0; i < 10; ++i)
            res.a[i] *= x;
        return res;
    }

    Result operator + (Result r) const {
        for(int i = 0; i < 10; ++i)
            r.a[i] += a[i];
        return r;
    }

    Result operator - (Result r) const {
        for(int i = 0; i < 10; ++i)
            r.a[i] = a[i] - r.a[i];
        return r;
    }

    void print() const {
        printf("%d", a[0]);
        for(int i = 1; i < 10; ++i)
            printf(" %d", a[i]);
        printf("\n");
    }
} c[10];

void init() {
    p10[0] = 1;
    for(int i = 1; i < 10; ++i)
        p10[i] = p10[i-1] * 10;
    for(int i = 1; i < 10; ++i) {
        c[i] = (c[i-1] * 10) + (Result(1) * p10[i-1]);
    }
}

char s[10];
Result calc(int x) {
    sprintf(s, "%d", x);
    int n = strlen(s);
    Result res, temp;
    for(int i = 0; i < n; ++i) {
        res = res + c[n-i-1] * (s[i] - 0x30);
        res = res + (temp * (s[i] - 0x30) + Result(1, s[i] - 0x30)) * p10[n-i-1];
        ++temp.a[s[i]-0x30];
    }
    res = res + temp;
    return res;
}

Result one(int x) {
    Result res;
    for(; x != 0; x /= 10) ++res.a[x%10];
    return res;
}

int main() {
    init();
    for(int x, y; scanf("%d%d", &x, &y) == 2 && (x | y); ) {
        if(x > y) swap(x, y);
        Result res;
        while(x <= y) {
            res = res + one(x);
            res = res + calc(min(y, *upper_bound(p10, p10+10, x) - 1)) - calc(x);
            x = *upper_bound(p10, p10+10, x);
        }
        res.print();
    }
    return 0;
}

Code mẫu của RR

//Written by RR
{$r-,q-}
{$mode objfpc}
{$inline on}

uses math;
const
  FINP          =       '';
  FOUT          =       '';
var
  f1,f2         :       text;
  a,b,now       :       longint;
  count         :       array[0..9] of int64;

procedure openF;
    begin
      assign(f1,FINP); reset(f1);
      assign(f2,FOUT); rewrite(f2);
    end;
procedure closeF;
    begin
      close(f1);
      close(f2);
    end;
procedure solve(n:longint);
    var
      last,i,m:longint;
    begin
      while (n>0) do
        begin
          last:=n mod 10; n:=n div 10;
          for i:=1 to last do inc(count[i],now);
          m:=n;
          while (m>0) do
            begin
              inc(count[m mod 10],(last+1)*now);
              m:=m div 10;
            end;
          for i:=0 to 9 do inc(count[i],n*now);
          now*=10; dec(n);
        end;
    end;

begin
  openF;
  read(f1,a,b);
  while (a>0) or (b>0) do
    begin
      fillchar(count,sizeof(count),0);
      now:=1;  solve(max(a,b));
      now:=-1; solve(min(a,b)-1);
      write(f2,count[0]);
      for a:=1 to 9 do
        write(f2,' ',count[a]);
      writeln(f2);
      read(f1,a,b);
    end;
  closeF;
end.

Code mẫu của hieult

#include <stdio.h>
//#include <conio.h>

int xuly(int x,int A)
{
    if(A == 0)
        return 0;
    int B = A, t = 0,mu10 = 1;
    while(B>=10)
    {
        B = B/10;
        t++;
        mu10 = mu10*10;
    }
    int y = A/mu10, a = (A - y*mu10);
    if(y<x)
         return y*t*(mu10/10) + xuly(x,a);
    else if(y>x)
         return mu10 + y*t*(mu10/10) + xuly(x,a);
    else if(y == x)
         return a+1+y*t*(mu10/10) + xuly(x,a);
}

int sochuso(int A)
{
    int KQ = 0;
    int B = A, t = 0,mu10 = 1;
    while(B>=10)
    {
        B = B/10;
        t++;
        mu10 = mu10*10;
    }
    for(int i = 1;i<=t;i++)
    {
        int nhan10 = 9*i;
        for(int j = 2;j<=i;j++)
            nhan10 = nhan10*10;
        KQ = KQ + nhan10;
    }
    KQ = KQ + (A-mu10+1)*(t+1);
    return KQ;
}

int main()
{
    int u[10],a,b;
    while(scanf("%d %d",&a,&b)>0 && a>0)
    {
        if(a>b)
        {
            int temp = a;
            a = b;
            b = temp;
        }
        int hieu = 0;
        for(int i = 1;i<=9;i++)
        {
            u[i] = xuly(i,b)- xuly(i,a-1);
            hieu = hieu + u[i];
        }
        u[0] = sochuso(b) - sochuso(a-1) - hieu;
        for(int i = 0;i<=9;i++)
            printf("%d ",u[i]);
        printf("\n");
    }
   // getch();
}

Code mẫu của ll931110

Program MDIGITS;
        Const
                input  = '';
                output = '';
                  maxd = 9;
        Var
                fi,fo: text;
                    p: array[0..maxd] of longint;
                    F: array[0..9,0..9] of longint;
             da,db,dc: array[0..maxd] of longint;
                a,b,t: longint;

Procedure openfile;
          Begin
                Assign(fi, input);
                        Reset(fi);

                Assign(fo, output);
                        Rewrite(fo);
          End;

Procedure gens;
          Var
                i,j: longint;
          Begin
                p[0]:= 1;
                For i:= 1 to maxd do p[i]:= p[i - 1] * 10;

                For i:= 0 to 9 do F[i,1]:= 1;
                For i:= 2 to 9 do
                  For j:= 0 to 9 do F[j,i]:= F[j,i - 1] * 10 + p[i - 1];
          End;

Procedure solve(x: longint);
          Var
                i,j,k,digit: longint;
          Begin
                Fillchar(dc, sizeof(dc), 0);
                If x < 10 then
                  Begin
                      For i:= 0 to x do dc[i]:= 1;
                      exit;
                  End;

                digit:= 1;
                While p[digit] <= x do inc(digit);

                dc[0]:= 0;
                For i:= 1 to digit - 1 do dc[0]:= dc[0] - p[i];

                While digit >= 1 do
                  Begin
                        k:= 0;
                        While (k + 1) * p[digit - 1] <= x do
                          Begin
                            dc[k]:= dc[k] + p[digit - 1];
                            For j:= 0 to 9 do dc[j]:= dc[j] + F[j,digit - 1];
                            inc(k);
                          End;

                        x:= x - p[digit - 1] * k;
                        dc[k]:= dc[k] + x + 1;
                        dec(digit);
                  End;
          End;

Procedure printresult;
          Var
                i: longint;
          Begin
                solve(a - 1);
                da:= dc;

                solve(b);
                db:= dc;

                For i:= 0 to 9 do write(fo, db[i] - da[i], ' ');
                Writeln(fo);
          End;

Procedure closefile;
          Begin
                Close(fo);
                Close(fi);
          End;

Begin
        openfile;
        gens;

        Repeat
             Read(fi, a, b);
             If a > b then
                Begin
                        t:= a;
                        a:= b;
                        b:= t;
                End;
             If (a <> 0) or (b <> 0) then printresult;
        Until (a = 0) and (b = 0);

        closefile;
End.

Code mẫu của skyvn97

#include<cstdio>
typedef long long ll;
struct ndigit {
    ll d[11];
};
ll p[11];
ndigit f[11];
ndigit g[11];
ll a,b;
void init(void) {
    int i,j;
    p[0]=1;
    for (i=1;i<=9;i=i+1) p[i]=p[i-1]*10;
    for (i=0;i<=9;i=i+1) {
        f[1].d[i]=1;
        g[1].d[i]=1;
        f[0].d[i]=0;
        g[0].d[i]=0;
    }
    for (i=2;i<=9;i=i+1)
        for (j=0;j<=9;j=j+1) f[i].d[j]=10*f[i-1].d[j]+p[i-1];
    for (i=2;i<=9;i=i+1)
        for (j=0;j<=9;j=j+1) g[i].d[j]=g[i-1].d[j]+9*f[i-1].d[j]+p[i-1]*(j>0);
}
int ndgs(ll x) {
    int i=1;
    while (p[i]<=x) i=i+1;
    return (i);
}
ndigit count(ll x) {
    ndigit res;
    if (x<10) {
        int i;
        for (i=0;i<=9;i=i+1) res.d[i]=(i<=x);
        return (res);
    }
    int dig[11];
    int i,j,k;
    int nd=0;
    while (x>0) {
        nd++;
        dig[nd]=x%10;
        x=x/10;
    }
    res=g[nd-1];
    for (i=nd;i>0;i=i-1)
        for (j=(i==nd);j<dig[i]+(i==1);j=j+1) {
            for (k=nd;k>i;k=k-1) res.d[dig[k]]+=p[i-1];
            res.d[j]+=p[i-1];
            for (k=0;k<=9;k=k+1) res.d[k]+=f[i-1].d[k];
        }
    return (res);
}
void swap (ll &a,ll &b) {
    ll sw;
    sw=a;a=b;b=sw;
}
void process(void) {
    if (a>b) swap(a,b);
    ndigit t1=count(a-1);
    ndigit t2=count(b);
    int i;
    for (i=0;i<9;i=i+1) printf("%lld ",t2.d[i]-t1.d[i]);
    printf("%lld\n",t2.d[9]-t1.d[9]);
}
int main(void) {
    init();
    while (true) {
        scanf("%lld",&a);
        scanf("%lld",&b);
        if (a==0 || b==0) return 0;
        process();
    }
}

Comments

Please read the guidelines before commenting.


There are no comments at the moment.