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.

Download