Hướng dẫn giải của Counting Digits


Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

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();
    }
}

Bình luận

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.