MDIGITS - Counting Digits
Tác giả: skyvn97
Ngôn ngữ: C++
#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();
}
}