DEMSO - Đếm số
Tác giả: hieult
Ngôn ngữ: C++
#include <cstdio>
//#include <conio.h>
#include <math.h>
long long A,B,F[20][20][20];
int d,K;
long long TTD(long long x)
{
if (x<0) return -x;
return x;
}
long long xuly(long long x)
{
int a[20],b[20],t=0;
long long the=x,KQ=0;
while(the!=0)
{
b[++t]=the%10;
the = the/10;
}
for(int i = 1;i<=t;i++) a[i] = b[t+1-i];
for(int i = 1;i<t;i++)
for(int j = 1;j<=9;j++)
for(int k = 0;k<=K;k++)
KQ = KQ+F[i][j][k];
// printf("%d\n",KQ);
int KK = K;
for(int i = 1;i<=t;i++)
{
if(i>2 && TTD(a[i-1]-a[i-2])<=d)
KK--;
if(KK<0) {break;}
int KKK;
if(i==1)
{
for(int j = 1;j<a[i];j++)
for(int k = 0;k<=KK;k++)
KQ = KQ+ F[t+1-i][j][k];
}
else
{
for(int j = 0;j<a[i];j++)
{
if(TTD(a[i-1]-j)<=d)
KKK = KK-1;
else KKK = KK;
for(int k = 0;k<=KKK;k++)
KQ = KQ+ F[t+1-i][j][k];
}
}
}
return KQ;
}
bool check(long long x)
{
int a[20],b[20],t=0,so=0;
long long the=x,KQ=0;
while(the!=0)
{
b[++t]=the%10;
the = the/10;
}
for(int i = 1;i<=t-1;i++)
if(TTD(b[i+1]-b[i])<=d)
so++;
if(so>K)
return false;
else return true;
}
int main()
{
//printf("*** %lld\n",F[2][1][0]);
scanf("%lld %lld %d %d",&A,&B,&d,&K);
for(int i = 0;i<=9;i++)
F[1][i][0] = 1;
for(int i =0;i<=9;i++)
for(int j = 1;j<=15;j++)
F[1][i][j] = 0;
for(int i = 2;i<=15;i++)
for(int j = 0;j<=9;j++)
for(int k = 0;k<=15;k++)
{
F[i][j][k]=0;
for(int u = 0;u<=9;u++)
{
if(TTD(j-u)>d)
F[i][j][k]+= F[i-1][u][k];
else if(k>0)F[i][j][k]+= F[i-1][u][k-1];
// if(i==2 && j==1 &&k==0)
// printf("%d %d\n",u,F[i][j][k]);
}
}
if(!check(B))
printf("%lld",xuly(B)-xuly(A));
else printf("%lld",xuly(B)-xuly(A)+1);
// int sa = 0;
//for(int i = A;i<=B;i++)
// if(check(i))
// ++sa;
// printf("\n%d",sa);
//getch();
}