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.