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.

Download