You are in a maze; seeing n doors in front of you in the beginning. You can choose any door you would like. The probability for choosing a door is equal for all the doors.

If you choose the i^th door, it can either take you back to the same position where you began in x_i minutes, or can take you out of the maze after x_i minutes. If you come back to the same position, you can't remember anything. So, every time you come to the beginning position, you have no past experience.

Now, you want to find the expected time to get out of the maze.

Input

Input starts with an integer T (≤ 100), denoting the number of test cases.

Each case contains a blank line and an integer n (1 ≤ n ≤ 100) denoting the number of doors. The next line contains n space separated integers. If the i^th integer (x_i) is positive, you can assume that the i^th door will take you out of the maze after x_i minutes. If it's negative, then the i^th door will take you back to the beginning position after abs(x_i) minutes. You can safely assume that 1 ≤ abs(x_i) ≤ 10000.

Output

For each case, print the case number and the expected time to get out of the maze. If it's impossible to get out of the maze, print inf. Print the result in p/q format. Where p is the numerator and q is the denominator of the result respectively. p and q should be relatively prime. See the samples for details.

Sample

Sample Input	Sample Output
Click to copy 3 1 1 2 -10 -3 3 3 -6 -9	Click to copy Case 1: 1/1 Case 2: inf Case 3: 18/1

LOJ 1027 - A Dangerous Maze

Before reading this tutorial I would suggest you to read this article for a better understanding of Mathematical Expectation

By the definition of Mathematical Expectation,
If P(i) represents probability of choosing door i and T(i) represents time to get out of the maze if we choose door i,
then for n number of doors,
Mathematical Expectation,
E = P(1)*T(1) + P(2)*T(2) + P(3)*T(3) + ...... + P(n)*T(n)

Let's begin with analyzing the 3rd test of the sample test case. The 3rd test case is -

3
3 -6 -9

Here, we are given 3 doors. And we can only get out of the maze by the first door with a cost of 3 minutes. Where, the 2nd and 3rd door would return us to the same position costing 6 minutes and 9 minutes respectively.
Let's assume the final expected time be E, what is our answer.
So here,
E = P(1)*T(1) + P(2)*T(2) + P(3)*T(3)

Each time we can randomly choose 1 door out of 3 doors and choosing one door is an independent event.
So, probability of choosing any door would be 1/3.
Thus, P(i) = 1/3, for i = 1, 2, 3
Now, we need to calculate T(i) for i = 1, 2, 3

If i = 1 i.e if we choose 1st door it would take us straight out of the maze. So T(1) = 3
If i = 2 i.e if we choose 2nd door it would take 6 minutes but would return us to the same position!
So, sadly we would have to start the whole process once again. As we assumed before that the final expected time is E, therefore we can safely say that for starting the whole process once again we will need E minutes more!
Thus time to get out of the maze if we choose 2nd gate
T(2) = Time to return to the same position + Expected time to get out of the maze for starting the process from beginning Therefore, T(2) = 6 + E
Similiarly, if i = 3, T(3) = 9 + E

So, finally,
E = (1/3)*3 + (1/3)*(6 + E) + (1/3)*(9 + E)
E = (1/3)*(3 + 6 + 9) + (1/3)*(E + E)
(1/3)*(3*E - 2*E) = (1/3)*(3 + 6 + 9)
E*(3 - 2) = (3 + 6 + 9) (Diving both sides by 1/3)
and, E = (3 + 6 + 9)/(3 - 2) ......... (1)
which ultimately yields, E = 18 / 1, which is our answer.

If we look at equation (1), we can see,
3 + 6 + 9 is the sum of absolute value of time taken by each door.
And, 3 is the number of doors and 2 is the number of reverse doors (doors that returns to the same postion). In other word, (3-2) is the number of doors that can get us out of the maze.

So, now we can have a generalized solution for this problem,
E = (sum of absolute value of the given times) / (number of gates that can take us out of the maze)

As, the output format is p/q, so both the the numbers divded by their GCD will be the ultimate solution.

Special Case

If there is no gate that can take us out of the maze, we would never get out of the maze! So, the ans would be inf

Time Complexity

As we are using an equation to solve the problem the time complexity would be simply of O(n)

Solution in C++

#include<iostream>
#include<math.h>
#include<algorithm>
#include<vector>
#include<set>
#include<queue>
using namespace std;
typedef long long ll;
#define endl '\n'
#define scan(n) scanf("%lld", &n);
#define print(n) printf("%lld", n);
#define pb(n) push_back(n)

void compute(ll a, ll b){
    ll x = __gcd(a,b);
    printf("%lld/%lld\n",a/x,b/x);
}

int main()
{
    ll t, no = 1;
    scan(t);
    while(t--){
        ll n;
        scan(n);
        ll a[n], sum = 0;
        for(ll i=0; i<n; i++) {
            scan(a[i]); sum+=abs(a[i]);
        }
        ll neg_sum = 0;
        for(ll i=0; i<n; i++){
            if(a[i]<0) neg_sum++;
        }
        printf("Case %lld: ",no++);
        if(neg_sum == n) printf("inf\n");
        else compute(sum,n-neg_sum);
    }
    return 0;
}

Tutorial source