JEDNAKOS - JEDNAKOST

Tác giả: flashmt

Ngôn ngữ: Pascal

uses math;
const maxn=1010;
      oo=1000000;
var s,n,l:longint;
    a:ansistring;
    f:array[0..maxn,0..maxn*5] of longint;
    p:array[1..4] of longint;
    b:array['0'..'9'] of longint;
    g:array[0..maxn,0..maxn*5] of longint;

procedure rf;
var i:longint; st:ansistring; code:integer;
begin
     readln(a);
     for n:=1 to length(a) do
         if a[n+1]='=' then break;
     st:='';
     for i:=n+2 to length(a) do
         st:=st+a[i];
     l:=length(st);
     val(st,s,code);
end;

procedure init;
var i,j:longint; c:char;
begin
     p[1]:=1;
     for i:=2 to 4 do p[i]:=p[i-1]*10;
     for c:='0' to '9' do b[c]:=ord(c)-48;
     for i:=0 to n do
         for j:=0 to s do
             f[i,j]:=oo;
     for j:=0 to s do g[0,j]:=oo;
     f[0,0]:=0;
end;

procedure pr;
var i,j,k,x:longint;
begin
     for i:=1 to n do
     begin
          x:=0;
          for j:=1 to 4 do
          begin
               if i<j then break;
               x:=x+p[j]*b[a[i-j+1]];
               for k:=x to s do
                   f[i,k]:=min(f[i,k],f[i-j,k-x]+1);
          end;
          if x=0 then
          begin
               g[i]:=g[i-1];
               continue;
          end;
          j:=j+1;
          if (i>=j) and (a[i-j+1]='0') then
          begin
               for k:=x to s do
                   f[i,k]:=min(f[i,k],g[i-j+1,k-x]+1);
          end;
          if a[i]='0' then
          begin
               if (i>1) and (a[i-1]='0') then
               begin
                    for j:=0 to s do
                        g[i,j]:=min(g[i-1,j],f[i,j]);
               end
               else
               begin
                    for j:=0 to s do
                        g[i,j]:=min(f[i,j],f[i-1,j]);
               end;
          end;
     end;
     if a[n]='0' then f[n,s]:=min(f[n,s],g[n,s]+1);
     writeln(f[n,s]-1);
end;

begin
     rf;
     init;
     pr;
end.

Download