DEMSO - Đếm số
Tác giả: RR
Ngôn ngữ: Pascal
{$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.