COIN34 spoj - 34 Đồng Xu - Kiến Thức 24h

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

Nội dung bài viết

1. Đề bài COIN34 spoj
2. Hướng dẫn COIN34 spoj 34 đồng xu
3. Code tham khảo COIN34 spoj 34 đồng xu

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ụ

<b>Dữ liệu</b>
4
1
5
8
9

<b>Kết quả</b>
Case #1: -1
Case #2: 2
Case #3: 2
Case #4: -1

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 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.

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;

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.

COIN34 spoj – 34 Đồng Xu

1. Đề bài COIN34 spoj

Dữ liệu

Kết quả

Ví dụ

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

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

Bài viết liên quan

Trả lời Hủy