DEMSO - Đếm số

Tác giả: flashmt

Ngôn ngữ: Pascal

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.

Download