DEMSO – SPOJ

const
  fi='';
  fo='';
  maxn=20;
var
  a,b,tg1,tg2 : int64;
  aa : array[1..maxn] of longint;
  i,j,n,k,d : longint;
  f : array[0..maxn,0..maxn,0..maxn,false..true,false..true] of int64; 
procedure swap(var x,y : longint);
  var tg : longint;
  begin
    tg:=x;x:=y;y:=tg;
  end;
procedure chuanbi(x : int64; var n : longint);
  var i,j : longint;
  begin
    n := 0;
    while x>0 do
      begin
        inc(n); aa[n] := x mod 10;
        x := x div 10;
      end;
    i:=1; j:=n;
    while (i<j) do
      begin
        swap(aa[i],aa[j]);
        inc(i);dec(j);
      end;
  end;
function tinh(i,tr,sl : longint; big0, small :boolean) : int64;
  var j,tg : longint;
      dem : int64;
  begin
    if f[i,tr,sl,big0,small] > -1 then exit(f[i,tr,sl,big0,small]);
    if i>n then
      if (sl<=k) and (small)  then exit(1) else exit(0);
    dem := 0;
    if not small then
      begin
        for j := 0 to aa[i] do
          begin
            if big0 then tg := sl + ord(abs(j-tr)<=d) else tg := 0;
            dem := dem + tinh(i+1,j,tg,big0 or (j>0),small or (j<aa[i]));
          end;
      end
      else
      begin
        for j := 0 to 9 do
          begin
            if big0 then tg := sl + ord(abs(j-tr)<=d) else tg := 0;
            dem := dem + tinh(i+1,j,tg,big0 or (j>0),small or (j<aa[i]));
          end;
      end;
    f[i,tr,sl,big0,small] := dem;
    exit(dem);
  end;
begin
  assign(input,fi);reset(input);
  assigN(output,fo);rewrite(output);
 
  readln(a,b,d,k);
 
  chuanbi(a, n);
 
  fillchar(f,sizeof(f),255);
  tg1 := tinh(1,0,0,false,false);
 
  chuanbI(b+1, n);
 
  fillchar(f,sizeof(f),255);
  tg2 := tinh(1,0,0,false,false);
 
  writeln(tg2-tg1);
 
  close(input);close(output);
end.

#include <bits/stdc++.h>
#define FORE(i, a, b) for(int i = a; i <= b; i++)
#define FORD(i, a, b) for(int i = a; i >= b; i--)
#define FOR(i, a, b) for(int i = a; i < b; i++)
const int MAXN = 1e5 * 5;
const int INF = 1e9 + 7;
 
using namespace std;
 
long long l, r, D, K, n;
long long f[20][10][20][2][2];
int a[20];
 
bool check(long long x)
{
    bool ans = 1;
    int top = 0;
    int tmp = x;
    while (tmp){
        a[++top] = tmp % 10;
        tmp /= 10;
    }
    reverse(a + 1, a + top + 1);
    int dem = 0;
    FORE(i, 2, top) if (abs(a[i] - a[i - 1]) <= D) dem++;
    //if (x == 103) cout << dem<<" "<<K<<"??"<<endl;
    return (dem <= K);
}
 
long long trau()
{
    long long ans = 0;
    FORE(i, l, r) if (check(i)) ans++;
    cout << ans << endl;
    return 0;
}
long long duyet(int i, int dig, int worse, bool ok, bool greater0)
{
    if (i > n){
        return (worse <= K && greater0 > 0);
    }
    if (f[i][dig][worse][ok][greater0] > -1) return f[i][dig][worse][ok][greater0];
 
    long long ans = 0;
    if (i == 1){
        FORE(x, 0, a[i]) ans += duyet(i + 1, x, worse, ok | (x < a[i]), (x > 0));
    } else {
        int last = 9;
        if (ok == 0) last = a[i];
        int wnext;
        //if (i == 3) cout << last << "??"<<endl;
        FORE(x, 0, last) {
            if (greater0 == 0) wnext = worse; else wnext = worse + (abs(x - dig) <= D);
            //if (last == 3) cout << x<< ' '<<dig<<" "<<wnext<<endl;
            ans += duyet(i + 1, x, wnext, ok | (x < a[i]), greater0 | (x > 0));
        }
    }
    f[i][dig][worse][ok][greater0] = ans;
    return ans;
}
 
int main()
{
    ios::sync_with_stdio(0); cin.tie(0);
    #ifndef ONLINE_JUDGE
    freopen("DEMSO.inp", "r", stdin);
    freopen("DEMSO.out", "w", stdout);
    #endif //MIKELHPDATKE
    cin >> l >> r >> D >> K;
    //trau();
 
    long long tmp = r, top = 0;
    while (tmp){
        a[++top] = tmp % 10;
        tmp /= 10;
    }
    reverse(a + 1, a + top + 1); n = top;
    memset(f, -1, sizeof(f));
 
    long long ans = duyet(1, 0, 0, 0, 0);
   // cout << ans << endl;
 
    tmp = l - 1, top = 0;
    while (tmp){
        a[++top] = tmp % 10;
        tmp /= 10;
    }
    reverse(a + 1, a + top + 1); n = top;
    memset(f, -1, sizeof(f));
    if (l - 1 == 0) cout << ans;
    else{
        ans -= duyet(1, 0, 0, 0, 0);
        cout << ans;
    }
    //cout<<check(103)<<endl;
    return 0;
}