COIN34 - 34 đồng xu
Tác giả: ladpro98
Ngôn ngữ: Pascal
program coin34;//backtrack
uses math;
type e=record
v,c:longint;
end;
const fi='';
var a:array[1..34] of longint;
save:array[0..10000000] of byte;
f:array[1..1 shl 15] of e;
d:longint;
n,limit,res,t,tt:longint;
inp:text;
procedure back1(i,s,c:longint);
begin
if i=limit then
begin
save[s]:=max(save[s],c);
exit;
end;
back1(i+1,s,c);
back1(i+1,s+a[i],c+1);
end;
procedure back2(i,s,c:longint);
begin
if i=limit then
begin
inc(d);
f[d].v:=s;
f[d].c:=c;
exit;
end;
back2(i+1,s,c);
back2(i+1,s+a[i],c+1);
end;
procedure init;
var i:longint;
begin
a[1]:=2;a[2]:=3;a[3]:=5;
for i:=4 to 34 do
a[i]:=a[i-1]+a[i-2]+a[i-3];
limit:=21;
back1(1,0,0);
limit:=35;
back2(21,0,0);
end;
procedure process;
var i,p,t:longint;
begin
res:=-1;
if n<=10000000 then
if save[n]<>0 then
res:=save[n];
for i:=2 to d do
begin
t:=n-f[i].v;
if t=0 then
res:=max(res,f[i].c)
else
if (1<=t) and (t<=10000000) then
begin
p:=save[t];
if p<>0 then
res:=max(res,p+f[i].c);
end;
end;
end;
begin
init;
assign(inp,fi);
reset(inp);
readln(inp,t);
for tt:=1 to t do
begin
readln(inp,n);
process;
writeln('Case #',tt,': ',res);
end;
end.