34 đồng xu

View as PDF
Submit solution
Points: 0.18 (partial)
Time limit: 1.0s
Memory limit: 512M
Input: stdin
Output: stdout
Problem source:
NUS ACM Training
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

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~
  • ~xu(n)~ có giá trị ~\left(xu(n-1) + xu(n-2) + xu(n-3)\right)~

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

Input

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 \left(1 \leq X \leq 2\,000\,000\,000\right)~.

Output

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

Sample Input

4
1
5
8
9

Sample Output

Case #1: -1
Case #2: 2
Case #3: 2
Case #4: -1

Comments

Please read the guidelines before commenting.