JEDNAKOS - JEDNAKOST

Tác giả: RR

Ngôn ngữ: Pascal

{$R+,Q+}
uses math;
const
  FINP='';
  FOUT='';
  MAXN=1001;
  MAXK=5001;
  so:array['0'..'9'] of longint=(0,1,2,3,4,5,6,7,8,9);
var
  first,last,sum,n:longint;
  s:ansistring;
  qs,qi,qd:array[1..MAXN*MAXK] of longint;
  xet:array[0..MAXK,1..MAXN] of longint;
  check:array[1..MAXN] of byte;
  f1,f2:text;
procedure openF;
begin
  assign(f1,FINP); reset(f1);
  assign(f2,FOUT); rewrite(f2);
end;
procedure closeF;
begin
  close(f1); close(f2);
end;
procedure inp;
var
  ss:ansistring;
  code:integer;
  i:longint;
begin
  readln(f1,ss);
  s:=copy(ss,1,pos('=',ss)-1); n:=length(s);
  delete(ss,1,pos('=',ss));
  val(ss,sum,code);
  check[n+1]:=1;
  for i:=n downto 1 do
    if (check[i+1]=1) and (s[i]='0') then check[i]:=1
    else break;
end;
procedure solve;
var
  u,i,uu,ii,d,sl,x:longint;
begin
  first:=1; last:=1; qs[1]:=sum; qi[1]:=1; qd[1]:=0;
  while first<=last do
    begin
      u:=qs[first]; i:=qi[first]; d:=qd[first]; inc(first);
      if (u=0) and (check[i]=1) then
        begin
          if i<n+1 then inc(d);
          writeln(f2,d-1); exit;
        end;
      sl:=n+1-i; x:=0; ii:=i;
      for sl:=1 to sl do
        begin
          x:=x*10+so[s[ii]]; uu:=u-x; inc(ii);
          if x=0 then continue;
          if (uu<0) then break;
          if xet[uu,ii]=0 then
            begin
              xet[uu,ii]:=1;
              inc(last); qs[last]:=uu; qi[last]:=ii; qd[last]:=d+1;
            end;
        end;
    end;
end;
begin
  openF;
  inp;
  solve;
  closeF;
end.

Download