LightOJ - 1027 A Dangerous Maze —— 期望

題目鏈接：https://vjudge.net/problem/LightOJ-1027

?

1027 - A Dangerous Maze

???

PDF (English)

Statistics

Forum

Time Limit:?2 second(s)

Memory Limit:?32 MB

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?n?space separated integers. If the?i^th?integer?(x_i)?is positive, you can assume that the?i^thdoor 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	Output for Sample Input
3 ? 1 1 ? 2 -10 -3 ? 3 3 -6 -9	Case 1: 1/1 Case 2: inf Case 3: 18/1

?

?

題意：

有n扇門，一扇門要么能在特定時間內把人帶出迷宮，要么能在特定時間內把人帶會原地，并使人失去記憶（即不知道這扇門是不能帶出迷宮的），每扇門被選擇的幾率是相等的。問走出迷宮的平均時間。

?

題解：

設期望為EX，有t1扇“正門”，t2扇“負門”，其中t1+t2 = n 。第i扇門所花費的時間為ai

1.當選擇的門為正門時，它可以直接走出迷宮，因此：1/n*ai，1/n為選擇這扇門的幾率，且所有的門被選擇的幾率也為1/n。

2.當選擇的門為負門時，它先花費了ai的時間，然后又重新選擇，重新選擇然能走出迷宮的時間即為平均時間，因此：1/n*(ai+EX)。

3.綜上，EX =?∑1/n*ai +?∑1/n*(ai+EX)，其中第一個i的范圍為：1<=i<=t1，第二個i：1<=i<=t2。

?

代碼如下：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <string>
#include <set>
using namespace std;
typedef long long LL;
const int INF = 2e9;
const LL LNF = 9e18;
const int MOD = 1e9+7;
const int MAXN = 1e6+100;

int gcd(int a, int b)
{
    return b==0?a:gcd(b,a%b);
}

int main()
{
    int T, n, kase = 0;
    scanf("%d", &T);
    while(T--)
    {
        scanf("%d", &n);
        int numP = 0, sum = 0;
        for(int i = 1; i<=n; i++)
        {
            int val;
            scanf("%d", &val);
            sum += abs(val);
            if(val>0) numP++;
        }
        if(numP==0)
            printf("Case %d: inf\n", ++kase);
        else
            printf("Case %d: %d/%d\n", ++kase, sum/gcd(sum, numP), numP/gcd(sum, numP));
    }
}

?