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);
     read(a,b,d,k);
     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;
}

Code mẫu của ladpro98

#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;
procedure readInput;
var
  f:text;
  ch:string[1];
  code:shortint;
begin
  assign(f,fi); reset(f);
  repeat
    read(f,ch);
    if ch<>' ' then begin inc(a[0]); val(ch,a[a[0]],code); end;
  until ch=' ';
  repeat
    read(f,ch);
    if ch<>' ' then begin inc(b[0]); val(ch,b[b[0]],code); end;
  until ch=' ';
  readln(f,d,k);
  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
  readInput;
  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;
}