100827E – Codeforces

Đề bài:

Thuật toán:

  • Bài này sử dụng phương pháp đệ quy có nhớ
  • Bạn có thể đọc code bên dưới để hiểu rõ hơn

Code:

uses math;
const
  fi='';
  fo='';
  maxn=80;
var
  f : array[0..maxn,0..9,false..true,false..true,false..true] of int64;
  res : int64;
  i,j,n,tt,t : longint;
  ss : array[1..maxn] of longint;
  s,st : string;
function ok(s : string) : boolean;
  begin
    if s[1]<=s[2] then
      begin
        for i:=1 to length(s)-1 do if s[i]>s[i+1] then break;
        if (i=length(s)-1) then exit(true);
        for j:=i to length(s)-1 do
          if s[j+1]>s[j] then exit(false);
        exit(true);
      end
      else
      begin
        for i:=1 to length(s)-1 do if s[i]<s[i+1] then exit(false);
        {if (i=length(s)-1) then exit(true);
        for j:=i to length(s)-1 do
          if s[j+1]<s[j] then exit(false);  }
        exit(true);
      end;
  end;
function nhohon(x,y : string):boolean;
  begin
    while length(x)<length(Y) do x := '0'+x;
    while length(x)>length(y) do y:='0'+y;
    if x<y then exit(true) else exit(false);
  end;
function tinh(i,tr : longint; tangdan,nhohon,bigger0 : boolean) : int64;
  var j,last : longint;
      sl : int64;
  begin
    if f[i,tr,tangdan,nhohon,bigger0]>-1 then exit(f[i,tr,tangdan,nhohon,bigger0]);
    if i>n then
      if {nhohon and} bigger0 then exit(1) else exit(0);
    sl := 0;
    if nhohon then last := 9 else last := ss[i];
    if tangdan then
      begin
        for j:=tr to last do
          sl := sl + tinh( i+1,j,tangdan,(nhohon) or (j<ss[i]),(bigger0) or (j>0) );
        if bigger0 then
          for j:= min(tr-1,last) downto 0 do
            sl := sl + tinh(i+1,j,false,nhohon or (j<ss[i]),bigger0 or (j>0));
      end
      else
      begin
        for j:=min(last,tr) downto 0 do
          sl := sl + tinh(i+1,j,false,nhohon or (j<ss[i]),bigger0 or (j>0));
      end;
    f[i,tr,tangdan,nhohon,bigger0] := sl;
    exit(sl);
  end;
procedure process;
  var i : longint;
  begin
    n := length(s);
    //for i:=1 to n do ss[i] := ord(s[i])-ord('0');
    for i:=1 to n do ss[i] := ord(s[i])-48;
    fillchar(f,sizeof(f),255);
    res := tinh(1,0,true,false,false);
  end;
begin
  assign(input,fi);reset(input);
  assign(output,fo);rewrite(output);
  readln(t);
  for tt:=1 to t  do
    begin
      readln(s);
      if not(ok(s)) then begin writeln(-1);continue; end;
      process;
      writeln(res);
    end;
  close(input);close(output);
end.