Nguồn đề bài: http://vn.spoj.com/problems/COIN34/
Nội dung bài viết
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ụ
1 2 3 4 5 6 7 8 9 10 11 12 | <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 |
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:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 | 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. |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 | 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. |
Bài viết liên quan
- PTIT016E spoj PTIT – ACM PTIT 2016 E – Kỳ thi ACM/ICPC
- NKH spoj – Tách Từ
- P156SUME spoj PTIT – ROUND 6E – Ước chung của chuỗi
- P156SUMH spoj PTIT – ROUND 6H – Kim cương
- ALADDIN spoj – Aladdin
- PTIT013K spoj PTIT – SỐ NGUYÊN HỆ CƠ SỐ ACM
- P147PROB spoj PTIT – Pha nước cam
- P141PROB spoj PTIT – Tuần lễ công dân
- P132SUMJ spoj PTIT – SUM2 J – Hoán vị chữ số
- BCTHIDAU spoj PTIT – Thi đấu