JEDNAKOS - JEDNAKOST

Tác giả: khuc_tuan

Ngôn ngữ: Pascal

//{$Q+,R+,S+}
// {$APPTYPE CONSOLE}
 {$mode delphi}

uses math, sysutils;

var
    buf : array[0..2000] of char;
    a : PChar;
    cur, k, inf, i, j, s, na : integer;
    f : array[0..1000,0..5000] of integer;
    next : array[0..1000] of integer;

function IFF(a : boolean; b, c : integer) : integer;
begin
    if a then IFF := b else IFF := c;
end;
    
begin
    readln(buf);
    for i:=0 to 2000 do if buf[i]='=' then
    begin
        buf[i] := #0;
        a := @buf;
        s := StrToInt(PChar(@buf[i+1]));
    end;
    fillchar( f, sizeof(f), $1f);
    inf := f[0,0];
    f[0,0] := 0;
    na := Length(a);
    Dec(a);
    for i:=na downto 1 do
    begin
        if (i=na) or (a[i]<>a[i+1]) then next[i] := i + 1
        else next[i] := next[i+1];
    end;
    for i:=0 to na-1 do
        for j:=0 to s do
            if f[i,j] < inf then
            begin
                cur := 0;
                for k:=IFF(a[i+1]='0', next[i+1]-1, i+1) to na do
                begin
                    cur := cur * 10 + ord(a[k]) - 48;
                    if cur > s then break;
                    if cur + j <= s then
                        f[k, cur + j] := min( f[k, cur + j], f[i,j] + 1);
                end;
            end;
    writeln( f[na, s] - 1 );    
end.

Download