coin34

Xem PDF

Điểm: 900 (p) Thời gian: 2.0s Bộ nhớ: 1G Input: bàn phím Output: màn hình

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 \rightarrow\) \(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.\)

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 (1 \le X \le 2000000000)\).

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

Example

Test 1

Input
4
1
5
8
9
Output
Case #1: -1
Case #2: 2
Case #3: 2
Case #4: -1

Bình luận

Không có bình luận nào.