COIN34 spoj – 34 Đồng Xu

Nguồn đề bài: http://vn.spoj.com/problems/COIN34/

1. Đề bài COIN34 spoj

Bạn có 34 đồng xu có giá trị như sau:
xu(1) có giá trị 2
xu(2) có giá trị 3
xu(3) có giá trị 5
for n = 4 to 34
xu(n) có giá trị (xu(n-1) + xu(n-2) + xu(n-3))

Bạn hãy dùng nhiều đồng xu nhất để mua một món hàng có giá là X!

Dữ liệu

Dòng đầu tiên là số test (không quá 1000). Mỗi dòng tiếp theo chứa một số nguyên X (1 ≤ X ≤ 2000000000).

Kết quả

Với mỗi test, in ra “Case #” + số hiệu test + “: ” + số lượng lớn nhất đồng xu cần dùng. Nếu không có cách nào để đạt giá trị X thì in ra -1.

Ví dụ

Dữ liệu
4
1
5
8
9

Kết quả
Case #1: -1
Case #2: 2
Case #3: 2
Case #4: -1

2. Hướng dẫn COIN34 spoj 34 đồng xu

Thuật toán : Duyệt phân tập

Duyệt 2 phần : 1..20, và 21..34

3. Code tham khảo COIN34 spoj 34 đồng xu

* Đã bổ sung code của admin 

Code của admin:

const   fi='COIN34.inp';
        nmax=10000;
        maxx=367980;

type    data=longint;
var
        test,n:data;
        f:text;
        A:array[0..34] of data;
        B:array[0..maxx] of byte;
        res,x:data;


function max(a,b:byte):byte;
begin
        if a>b then exit(a);
        exit(b);
end;

procedure try1(i,s:data; slxu:byte);
begin
        if i>20 then exit;
        try1(i+1,s+a[i],slxu+1);
        b[s+a[i]]:=max(b[s+a[i]],slxu+1);
        try1(i+1,s,slxu);
end;

procedure try2(i,s:data; slxu:byte);
begin
        if i>34 then exit;
        try2(i+1,s+a[i],slxu+1);
        if (x-(s+a[i])>=0) and (x-(s+a[i])<=maxx)then
                begin
                        if ((x-(s+a[i])>=0) and (B[x-(s+a[i])]<>0)) or (x-(s+a[i])=0) then
                                res:=max(res,B[x-(s+a[i])]+slxu+1);
                end;
        try2(i+1,s,slxu);
end;

procedure docfile;
var     i,j:data;
begin
        A[1]:=2;
        a[2]:=3;
        a[3]:=5;
        fillchar(b,sizeof(b),0);
        for i:=4 to 34 do
                A[i]:=a[i-1]+a[i-2]+a[i-3];
        res:=0;
        for i:=1 to 20 do
                res:=res+a[i];
        res:=0;
        try1(1,0,0);
        assign(f,fi); reset(f);
        readln(f,test);
        for i:=1 to test do
                begin
                        res:=0;
                        readln(f,x);
                        if x<=maxx then
                                res:=B[x]
                        else
                                try2(21,0,0);
                        if res=0 then
                                res:=-1;
                        writeln('Case #',i,': ',res);
                end;
        close(f);
end;

begin
        docfile;
end.

const
        COIN    =       34;
        maxm    =       391230;
var
        n, res  :       byte;
        test, i,
        x       :       longint;
        a, t    :       array[0..coin] of longint;
        f       :       array[0..maxm] of byte;
        count   :       array[0..coin] of byte;


procedure init;
var     i : byte;
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];
end;

procedure duyet1(i : byte);
var     j : byte;
begin
        for j:= 0 to 1 do
        begin
                t[i]:= t[i-1]; count[i]:= count[i-1];
                if j=1 then
                begin
                        inc(t[i], a[i]); inc(count[i])
                end;
                if i < 20 then
                        duyet1(i+1)
                else    if count[i] > f[t[i]] then
                        f[t[i]]:= count[i]
        end;
end;

function max(a, b : byte): byte;
begin
        if a > b then
                max:= a
        else    max:= b
end;

procedure duyet2(i : byte);
var     j : byte;
begin
        for j:= 0 to 1 do
        begin
                t[i]:= t[i-1]; count[i]:= count[i-1];
                if j=1 then
                begin
                        inc(t[i], a[i]); inc(count[i]);
                end;
                if i < coin then
                        duyet2(i+1)
                else    if (x - t[i] >= 0) and (x - t[i] <= maxm) then
                        if ((x - t[i] > 0) and (f[x - t[i]] <> 0))
                           or (x - t[i] = 0) then
                                res:= max(res, f[x-t[i]] + count[i])
        end
end;


begin
        init;
        duyet1(1);
        readln(test);
        t[20]:= 0; count[20]:= 0;
        for i:= 1 to test do
        begin
                readln(x);
                res:= 0;
                if x <= maxm then
                        res:= max(res, f[x]);
                duyet2(21);
                if res=0 then
                        writeln('Case #', i, ': -1')
                else    writeln('Case #', i, ': ', res)
        end;
readln
end.