JEDNAKOS - JEDNAKOST

Tác giả: ll931110

Ngôn ngữ: Pascal

{$MODE DELPHI}
Program JEDNAKOS;
  Const
    input  = '';
    output = '';
    maxn = 1000;
    maxs = 5000;
    maxv = 100000000;
  Var
    c,F: array[0..maxn,0..maxs] of integer;
    last: array[0..maxn] of integer;
    a: string;
    n,s: integer;


Procedure init;
  Var
    fi: text;
    tmp,st: string;
    k,i,code: integer;
  Begin
    Assign(fi, input);
      Reset(fi);
      Readln(fi, st);
    Close(fi);

    k:= pos('=', st);
    tmp:= copy(st, k + 1, length(st) - k);
    val(tmp, s, code);

    delete(st, k, length(st) - k + 1);

    a:= '';
    k:= 0;
    For i:= 1 to length(st) do if st[i] <> '0' then
      Begin
        k:= 0;
        a:= a + st[i];
      End
    else
      Begin
        inc(k);
        If k <= 7 then a:= a + st[i];
      End;

    n:= length(a);
  End;

Procedure solve;
  Var
    st: string;
    i,j,k,x: integer;
    tmp,code: integer;
  Begin
    Fillchar(last, sizeof(last), 0);
    last[0]:= 1;

    For i:= 1 to n do
      For j:= 0 to s do F[i,j]:= maxv;

    c[0,1]:= 0;
    F[0,0]:= -1;

    For i:= 1 to n do
      Begin
        j:= i;
        st:= '';

        Repeat
          st:= a[j] + st;
          If (length(st) >= 5) and (a[j] <> '0') then break;
          val(st, x, code);

          For k:= 1 to last[j - 1] do
            Begin
              tmp:= c[j - 1,k] + x;
              If (tmp <= s) and (F[i,tmp] = maxv) then
                Begin
                  inc(last[i]);
                  c[i,last[i]]:= tmp;
                End;

              if (tmp <= s) and (F[i,tmp] > F[j - 1,c[j - 1,k]] + 1)
                then F[i,tmp]:= F[j - 1,c[j - 1,k]] + 1;
            End;

          dec(j);
        Until j = 0;
      End;
  End;

Procedure printresult;
  Var
    fo: text;
  Begin
    Assign(fo, output);
      Rewrite(fo);
      Writeln(fo, F[n,s]);
    Close(fo);
  End;

Begin
  init;
  solve;
  printresult;
End.

Download