Google Code Jam '08 Round 1A Problem C - Numbers

View as PDF

Submit solution

Points: 20 (partial)
Time limit: 30.0s
Memory limit: 1G

Problem type

In this problem, you have to find the last three digits before the decimal point for the number (3 + \sqrt{5})^n.

For example, when n = 5, (3 + \sqrt{5})^5 = 3935.73982... The answer is 935.

For n = 2, (3 + \sqrt{5})^2 = 27.4164079... The answer is 027.

Input Specification

The first line of input gives the number of cases, T. T test cases follow, each on a separate line. Each test case contains one positive integer n.

Output Specification

For each input case, you should output: Case #X: Y where X is the number of the test case and Y is the last three integer digits of the number (3 + \sqrt{5})^n. In case that number has fewer than three integer digits, add leading zeros so that your output contains exactly three digits.


Time limit: 30 seconds per test set.

Memory limit: 1 GB.

1 \le T \le 100.

Small Dataset

2 \le n \le 30.

Large Dataset

2 \le n \le 2\,000\,000\,000.

Sample Input


Sample Output

Case #1: 935
Case #2: 027


There are no comments at the moment.