DTDOI - Đổi tiền

Tác giả: RR

Ngôn ngữ: Pascal

//Written by RR
{$R+,Q+}
{$Mode objfpc}
{$inline on}
uses math;
const
  FINP          =       '';
  FOUT          =       '';
  MAXN          =       20111;

var
  f1,f2         :       text;
  n,s           :       longint;
  a             :       array[1..111] of longint;
  f             :       array[0..MAXN] of longint;

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
      i:longint;
    begin
      read(f1,n,s);
      for i:=1 to n do
        read(f1,a[i]);
    end;

procedure solve;
    var
      i,k:longint;
    begin
      fillchar(f,sizeof(f),$77);
      f[0]:=0;
      for i:=1 to MAXN do
      for k:=1 to n do
        if a[k]<=i then
          f[i]:=min(f[i],f[i-a[k]]+1);

      if s<=MAXN then
        writeln(f2,f[s])
      else
        begin
          k:=0;
          for i:=1 to n do
            k:=max(k,a[i]);
          i:=MAXN;
          while i mod k<>0 do dec(i); i:=i-k+s mod k;
          writeln(f2,f[i]+(s-i) div k);
        end;
    end;

begin
  openF;
  inp;
  solve;
  closeF;
end.

Download