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.
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