Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Recursive Function

By muntasir · Limits 1s, 512 MB

A common example of recursion goes something like this:

long long recur(int x){
	if (x==0){
        return X0;
	}
	else if (x==1){
        return X1;
	}
	else{
        long long t1=recur(--x);
        long long t2=recur(--x);
        return t1+t2;
	}
}

It is of course easy to calculate the value of this function for any x when the values of X0 and X1 are known. However, your task is to find the value of recur for a given number without being given the values of X0 and X1. Instead, you are given the values of recur(a) and recur(b) for given values of a and b.

Input

Input consists of several cases. The first line contains a single integer N, the number of test cases. N lines follow. Each line contains five integers, a,A,b,B and c, separated by spaces. A is the value of recur(a) and B is the value of recur(b).
You can assume that 0 ≤ a,b,c ≤ 50, a != b, and -1018 ≤ A,B ≤ 1018. Also, the value of recur(c), which you have to find, will always be such that -1018 ≤ recur(c) ≤ 1018.

There are at most 200 test cases.

Output

Output should consist of exactly N lines, one for each test case. Each line should be of the format Case #X: Y (without the quotes), where X is the test case and Y is the value of recur(c). See sample output for details.

Sample

InputOutput
4
0 0 1 1 40
0 -5 1 100 6
6 8 11 89 8
0 8 1 -5 50
Case #1: 102334155
Case #2: 775
Case #3: 21
Case #4: -701408733

Discussion

Statistics


63% Solution Ratio

Labib666Earliest, Feb '16

forthright48Fastest, 0.0s

forthright48Lightest, 131 kB

evonlochShortest, 863B

Submit

Login to submit

Toph uses cookies. By continuing you agree to our Cookie Policy.