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.

Download