DTDOI - Đổi tiền

Tác giả: flashmt

Ngôn ngữ: Pascal

const fi='';
      fo='';
      maxc=100000;
var n,s,re:longint;
    a:array[1..100] of longint;
    d:array[1..100] of byte;
    f:array[0..1,0..maxc] of longint;

procedure rf;
var i,t:longint;
begin
     assign(input,fi);
     reset(input);
     readln(n,s);
     fillchar(d,sizeof(d),0);
     for i:=1 to n do
     begin
          read(t); d[t]:=1;
     end;
     t:=0;
     for i:=1 to 100 do
         if d[i]>0 then
         begin
              inc(t); a[t]:=i;
         end;
     close(input);
end;

procedure knap;
var i,j,k,cur:longint;
begin
     for i:=0 to maxc do f[1,i]:=i;
     for i:=2 to n do
     begin
          cur:=i mod 2;
          f[cur]:=f[1-cur];
          for j:=1 to maxc do
              if (j>=a[i]) and (f[cur,j]>f[cur,j-a[i]]+1) then
                 f[cur,j]:=f[cur,j-a[i]]+1;
     end;
end;

procedure pr;
var i,j:longint;
begin
     knap;
     if s>maxc then
     begin
          re:=(s-maxc) div a[n];
          if (s-maxc) mod a[n]<>0 then inc(re);
          s:=s-re*a[n];
     end;
     re:=re+f[n mod 2,s];
end;

procedure wf;
begin
     assign(output,fo);
     rewrite(output);
     write(re);
     close(output);
end;

begin
     rf;
     pr;
     wf;
end.

Download