COIN34 - 34 đồng xu
Tác giả: flashmt
Ngôn ngữ: Pascal
const fi='';
fo='';
maxn=131071;
type ar=array[0..maxn] of longint;
var n,m,max,i,re,t,j:longint;
f,g,h,e,num:ar;
a,b:array[0..33] of longint;
p:array[0..17] of longint;
d:array[0..59138] of longint;
procedure sort(var f,h:ar;l,r:longint);
var x,y,i,j:longint;
begin
i:=l; j:=r; x:=f[(i+j) div 2];
repeat
while f[i]<x do i:=i+1;
while f[j]>x do j:=j-1;
if i<=j then
begin
y:=f[i]; f[i]:=f[j]; f[j]:=y;
y:=h[i]; h[i]:=h[j]; h[j]:=y;
i:=i+1; j:=j-1;
end;
until i>j;
if i<r then sort(f,h,i,r);
if l<j then sort(f,h,l,j);
end;
procedure init;
var i,j,t:longint;
begin
a[0]:=2; a[1]:=3; a[2]:=5; p[0]:=1;
for i:=3 to 33 do a[i]:=a[i-1]+a[i-2]+a[i-3];
for i:=0 to 16 do b[i]:=a[i+17];
for i:=1 to 17 do p[i]:=p[i-1] shl 1;
m:=16; max:=p[m+1]-1;
fillchar(f,sizeof(f),0);
fillchar(num,sizeof(num),0); e[0]:=0;
for i:=1 to max do
begin
t:=i; j:=0; e[i]:=i;
while t>0 do
begin
if t and 1=1 then
begin
f[i]:=f[i]+a[j];
inc(num[i]);
end;
inc(j);
t:=t shr 1;
end;
end;
fillchar(g,sizeof(g),0); h[0]:=0;
for i:=1 to max do
begin
h[i]:=i;
t:=i; j:=0;
while t>0 do
begin
if t and 1=1 then g[i]:=g[i]+b[j];
inc(j);
t:=t shr 1;
end;
end;
sort(f,e,0,max);
sort(g,h,0,max);
fillchar(d,sizeof(d),0);
for i:=0 to max do
if d[f[i]]=0 then d[f[i]]:=num[e[i]]
else
begin
if d[f[i]]<num[e[i]] then d[f[i]]:=num[e[i]];
end;
end;
begin
init;
assign(input,fi);
reset(input);
assign(output,fo);
rewrite(output);
readln(t);
for j:=1 to t do
begin
readln(n);
re:=-1;
for i:=0 to max do
if (g[i]<=n) and (n-g[i]<=59138) then
begin
if (d[n-g[i]]>0) then
begin
if num[h[i]]+d[n-g[i]]>re then re:=num[h[i]]+d[n-g[i]];
end;
end
else
begin
if g[i]>n then break;
end;
writeln('Case #',j,': ',re);
end;
close(output);
close(input);
end.