COIN34 - 34 đồng xu
Giới hạn- Thời gian: 0.34s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
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
- Người up: paulmcvn
- Nguồn bài: NUS ACM Training