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ụ

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:

 

Trả lời

Thư điện tử của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *