A Dangerous Maze

 LightOJ - 1027 

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

If you choose the i^th door, it can either take you back to the same position where you begun 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 nspace separated integers. If the i^th integer (x_i) is positive, you can assume that the i^th door will take you out of 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 of the result and q is the denominator of the result and they are relatively prime. See the samples for details.

Sample Input

3

1

1

2

-10 -3

3

3 -6 -9

Sample Output

Case 1: 1/1

Case 2: inf

Case 3: 18/1

题意：在n个门前选择一扇门出去， 然后如果第i扇门的 Xi值是正的话，你会花费Xi时间后出去 ，如果Xi是负数的话你会花费Xi时间后回到老地方，并且忘记了刚才的选择，选择一扇门的概率是等概的。求出去的期望。

题解：定义一次选择选择到Xi是整数的概率为P1,选择到负数的概率是P2，然后选择了正数后平均在T1时间后出去， 选择了负数后平均在T2时间后回到原地。接着设出去的期望是Y，那么可以写出一个式子 ：Y = P1 * T1 + P2 * (T2 + Y)

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 int a[110];
 7 int n;
 8 int time1,time2;
 9 int gcd(int a,int b)
10 {
11     if(b==0)
12         return a;
13     return gcd(b,a%b);
14 }
15 int main()
16 {
17     int casen,ca=1;
18     scanf("%d",&casen);
19     while(casen--)
20     {
21         int flag=0;
22         time1=0,time2=0;
23         int sum1=0,sum2=0;
24         scanf("%d",&n);
25         for(int i=1;i<=n;i++)
26         {
27             scanf("%d",&a[i]);
28             if(a[i]>0)
29             {
30                 flag=1;
31                 time1+=a[i];
32                 sum1++;
33             }
34             else      
35             {
36                 time2+=(-a[i]);
37                 sum2++;
38             }
39         }    
40         printf("Case %d: ",ca++);
41         if(!flag)
42         {
43             printf("inf\n");
44             continue;
45         }
46         else
47         {
48             int up=time1+time2;
49             int down=n-sum2; 
50             int g=gcd(up,down);
51             printf("%d/%d\n",up/g,down/g);
52         }
53     }
54 }