## Editorial for Đếm số

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

const fi='';
maxl=16;
var a,b:int64;
d,k,l:longint;
f,s,f0:array[1..maxl,0..9,-1..maxl] of int64;
c:array[1..maxl] of longint;

procedure dp;
var i,j,p,q:longint;
begin
for j:=0 to 9 do f[1,j,0]:=1;
for i:=2 to maxl do
for j:=0 to 9 do
for p:=0 to 9 do
for q:=0 to i-1 do
if abs(j-p)<=d then
f[i,j,q]:=f[i,j,q]+f[i-1,p,q-1]
else
f[i,j,q]:=f[i,j,q]+f[i-1,p,q];
f0:=f;
for i:=2 to maxl do
begin
for q:=0 to i-1 do f0[i,0,q]:=0;
for p:=0 to 9 do
for q:=0 to i-1 do
inc(f0[i,0,q],f0[i-1,p,q]);
end;
for i:=1 to maxl do
for j:=0 to 9 do
for q:=0 to maxl do
s[i,j,q]:=s[i,j,q-1]+f[i,j,q];
end;

function calc(a:int64):int64;
var i,j,kk:longint; st:string; re:int64;
begin
calc:=1+a; re:=0;
if a<10 then exit;
str(a,st); l:=length(st);
kk:=k;
for i:=1 to l do c[i]:=ord(st[i])-48;
for j:=0 to kk do re:=re+f0[l,0,j];
for j:=1 to c[1]-1 do re:=re+s[l,j,kk];
for i:=2 to l-1 do
begin
for j:=0 to c[i]-1 do
if abs(j-c[i-1])<=d then re:=re+s[l-i+1,j,kk-1]
else re:=re+s[l-i+1,j,kk];
if abs(c[i]-c[i-1])<=d then dec(kk);
if kk<0 then
begin
calc:=re; exit;
end;
end;
if l>1 then
for j:=0 to c[l] do
if (abs(j-c[l-1])>d) or (kk>0) then inc(re);
calc:=re;
end;

begin
assign(input,fi); reset(input);
close(input);
dp;
writeln(calc(b)-calc(a-1));
end.


#### Code mẫu của happyboy99x

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

typedef long long int64;
const int L = 20;
int64 f[L][L][10][2];

int lg10(int64 n) {
int res = 0;
while(n) n /= 10, ++res;
return res;
}

int64 calc(int64 n, int64 d, int64 k) {
if(n < 10) return n;
memset(f, 0, sizeof f);
int len = lg10(n);
k = min(k, len-1LL);
for(int v = 0; v < 10; ++v)
for(int diff = 0; diff <= k; ++diff) {
f[len-1][diff][v][1] = 1;
f[len-1][diff][v][0] = v == n % 10 ? 1 : 0;
}
int64 num = n;
for(int i = len-2; i >= 0; --i, num /= 10)
for(int diff = 0; diff <= k; ++diff)
for(int v = 0; v < 10; ++v) if(i | v)
for(int s = 0; s < 2; ++s)
for(int nx = 0; nx <= (s == 0 ? num % 10 : 9); ++nx)
f[i][diff][v][s] += f[i+1][diff + (abs(nx - v) <= d ? 1 : 0)][nx][s | (nx < num % 10 ? 1 : 0)];
int64 res = 0;
for(int s = 1; s <= num; ++s)
res += f[0][0][s][s < num ? 1 : 0];
return res;
}

int64 beautiful(int64 n, int64 d, int64 k) {
int64 res = calc(n, d, k);
for(int64 t = 10; t <= n; t *= 10)
res += calc(t-1, d, k);
return res;
}

int main() {
int64 a, b, d, k;
cin >> a >> b >> d >> k;
cout << beautiful(b, d, k) - beautiful(a-1, d, k) << endl;
return 0;
}


#include <bits/stdc++.h>
#define long long long
const int N = 25;
using namespace std;
long A, B, D, K;
long F[N][N][N];

long DP(long a) {
int digit[N], d = 0;
while (a) {digit[++d] = a % 10; a /= 10;}
reverse(digit + 1, digit + 1 + d);
long res = 0;
for(int i = 1; i < d; i++) for(int j = 0; j <= 9; j++)
for(int k = 0; k <= K; k++) res += F[i][j][k];
long C[N][N][N][2];
memset(C, 0, sizeof C);
//C[i][j][k][t] = use i digits, last one is j, k bad position to the left,
//t == 1 if the number if == a up to i
for(int j = 1; j <= digit[1]; j++) C[1][j][0][j < digit[1] ? 0 : 1] = 1;
for(int i = 1; i <= d; i++) for(int j = 0; j <= 9; j++)
for(int k = 0; k <= K; k++) for(int t = 0; t <= 1; t++) {
if (t == 0) {
for(int next = 0; next <= 9; next++)
C[i + 1][next][abs(next - j) <= D ? k + 1 : k][0] += C[i][j][k][0];
}
else  {
for(int next = 0; next <= digit[i + 1]; next++)
C[i + 1][next][abs(next - j) <= D ? k + 1 : k][next == digit[i + 1] ? 1 : 0] += C[i][j][k][t];
}
}
for(int j = 0; j <= 9; j++) for(int k = 0; k <= K; k++) for(int t = 0; t <= 1; t++)
res += C[d][j][k][t];
return res;
}

int main()
{
scanf("%lld %lld %lld %lld", &A, &B, &D, &K); K = min(K, 15ll);
//F[i][j][k] = use i digits, the last digit is j, and k bad position to the left
for(int j = 1; j <= 9; j++) F[1][j][0] = 1;
for(int i = 0; i <= 15; i++)
for(int j = 0; j <= 9; j++)
for(int k = 0; k <= K; k++)
for(int next = 0; next <= 9; next++)
if (abs(j - next) <= D) F[i + 1][next][k + 1] += F[i][j][k];
else F[i + 1][next][k] += F[i][j][k];
long res = DP(B) - DP(A - 1);
printf("%lld", res);
return 0;
}


#### Code mẫu của RR

{\$R+,Q+}
PROGRAM DEMSO;
CONST
fi='';
fo='';
TYPE
so=array[0..16] of integer;
VAR
a,b:so;
d,k:integer;
f:array[1..16,0..16,0..9,0..2] of int64;
var
f:text;
ch:string[1];
code:shortint;
begin
assign(f,fi); reset(f);
repeat
if ch<>' ' then begin inc(a[0]); val(ch,a[a[0]],code); end;
until ch=' ';
repeat
if ch<>' ' then begin inc(b[0]); val(ch,b[b[0]],code); end;
until ch=' ';
close(f);
end;
function cal(a:so):int64;
var
s,x,c,cc,tt:integer;
kq:int64=0;
begin
fillchar(f,sizeof(f),0);
for c:=0 to 9 do
if a[1]>c then f[1,0,c,0]:=1
else if a[1]=c then f[1,0,c,1]:=1
else f[1,0,c,2]:=1;
for s:=2 to a[0] do
for x:=0 to k do
for c:=0 to 9 do
for cc:=0 to 9 do
if (s>2) or (cc>0) then
begin
if abs(cc-c)>d then f[s,x,c,0]:=f[s,x,c,0]+f[s-1,x,cc,0]
else if x>0 then f[s,x,c,0]:=f[s,x,c,0]+f[s-1,x-1,cc,0];
if c<a[s] then
if abs(cc-c)>d then f[s,x,c,0]:=f[s,x,c,0]+f[s-1,x,cc,1]
else if x>0 then f[s,x,c,0]:=f[s,x,c,0]+f[s-1,x-1,cc,1];
if c=a[s] then
if abs(cc-c)>d then f[s,x,c,1]:=f[s,x,c,1]+f[s-1,x,cc,1]
else if x>0 then f[s,x,c,1]:=f[s,x,c,1]+f[s-1,x-1,cc,1];
if abs(cc-c)>d then f[s,x,c,2]:=f[s,x,c,2]+f[s-1,x,cc,2]
else if x>0 then f[s,x,c,2]:=f[s,x,c,2]+f[s-1,x-1,cc,2];
if c>a[s] then
if abs(cc-c)>d then f[s,x,c,2]:=f[s,x,c,2]+f[s-1,x,cc,1]
else if x>0 then f[s,x,c,2]:=f[s,x,c,2]+f[s-1,x-1,cc,1];
end;
for s:=1 to a[0]-1 do
for x:=0 to k do
for c:=0 to 9 do
for tt:=0 to 2 do
kq:=kq+f[s,x,c,tt];
for x:=0 to k do
for c:=0 to 9 do
kq:=kq+f[a[0],x,c,0];
cal:=kq;
end;
function ok(a:so):integer;
var
i,count:integer;
begin
count:=0;
for i:=1 to a[0]-1 do
if abs(a[i]-a[i+1])<=d then inc(count);
if count<=k then ok:=1 else ok:=0;
end;
procedure writeOutput;
var
f:text;
begin
assign(f,fo); rewrite(f);
writeln(f,cal(b)-cal(a)+ok(b));
close(f);
end;
BEGIN
writeOutput;
END.


#### Code mẫu của hieult

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


#### Code mẫu của skyvn97

#include<cstdio>
#include<cstring>
typedef long long ll;
struct num {
int nd;
int d[20];
num() {
nd=0;
}
num(ll x) {
nd=0;
while (x>0) {
nd++;
d[nd-1]=x%10;
x=x/10;
}
}
int operator [] (const int &i) const {
return (d[i]);
}
};
ll num9[20];
ll f[20][13][20][3];
ll a,b;
int d,k;
int abs(const int &x) {
if (x<0) return (-x); else return (x);
}
void init(void) {
int i;
num9[1]=9;
for (i=2;i<=17;i=i+1) num9[i]=(num9[i-1]+1)*10-1;
}
ll count(const ll &x,int m) {
if (x<1) return (0);
num tmp=num(x);
int n=tmp.nd;
//printf("%d\n",n);
if (m>=n) m=n-1;
int i,j,k,l,t;
for (i=1;i<17;i=i+1)
for (j=0;j<10;j=j+1)
for (k=0;k<17;k=k+1)
for (l=0;l<2;l=l+1)
f[i][j][k][l]=0;
for (i=1;i<=tmp[n-1];i=i+1) f[1][i][0][i<tmp[n-1]]=1;
for (i=1;i<n;i=i+1)
for (j=0;j<10;j=j+1)
for (k=0;k<i && k<=m;k=k+1)
for (l=0;l<2;l=l+1)
for (t=0;t<=(1-l)*tmp[n-i-1]+9*l;t=t+1) {
f[i+1][t][k+(abs(t-j)<=d)][l||(t<tmp[n-i-1])]+=f[i][j][k][l];
//printf("Updated f(%d,%d,%d,%d)=%lld to f(%d,%d,%d,%d)\n",i,j,k,l,f[i][j][k][l],i+1,t,k+(abs(t-j)<=d),l||(t<tmp[n-i-1]));
}
ll res=0;
for (j=0;j<10;j=j+1)
for (k=0;k<=m;k=k+1)
res+=f[n][j][k][1]+f[n][j][k][0];
//printf("Result is %lld\n",res);
return (res);
}
ll count(const ll &x) {
int i;
if (x<1) return (0);
//printf("Count %lld\n",x);
int n=num(x).nd;
ll res=0;
for (i=1;i<n;i=i+1) {
res+=count(num9[i],k);
//printf("%lld\n",res);
}
res+=count(x,k);
return (res);
}
void process(void) {
scanf("%lld",&a);
scanf("%lld",&b);
scanf("%d",&d);
scanf("%d",&k);
printf("%lld",count(b)-count(a-1));
}
int main(void) {
init();
process();
return 0;
}