LightOJ 1027 A Dangerous Maze (期望)

题目链接：LightOJ - 1027

Description

Input

Output

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

Solution

题意

你在一个迷宫里，面前有 \(n\) 扇门，如果第 \(i\) 扇门的 \(X_i\) 值为正值，就可以花费 \(X_i\) 的时间的走出迷宫，否则花费 \(abs(X_i)\) 的时间又回到原点，且不记得之前走过哪些门。每次等概率选择一扇门，问走出迷宫的时间的期望。不能走出去输出 \(inf\)。

思路

设有 \(n_1\) 扇门能走出迷宫，\(n_2\) 不能走出迷宫，则 \(n_1 + n_2 = n\)。

设 \(n_1\) 扇门的 \(X_i\) 值的平均值为 \(t_1\)，\(n_2\) 扇门的 \(X_i\) 值的平均值为 \(t_2\).

设走出去的期望为 \(E\)。则 \(E = \frac{n_1}{n} \cdot t_1 + \frac{n_2}{n} \cdot (t_2 + E)\)。

化简后为 \(E = \frac{1}{n_1}\sum_{i=1}^n abs(X_i)\)。

Code

#include <bits/stdc++.h>
using namespace std;
const int maxn = 110;

int x[maxn];

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;
    cin >> T;
    int kase = 0;
    while(T--) {
        int n;
        cin >> n;
        int sum = 0;
        int cnt = 0;
        for(int i = 1; i <= n; ++i) {
            cin >> x[i];
            if(x[i] > 0) {
                ++cnt;
                sum += x[i];
            } else {
                sum += -x[i];
            }
        }
        int d = gcd(sum, cnt);
        if(cnt == 0) printf("Case %d: inf\n", ++kase);
        else printf("Case %d: %d/%d\n", ++kase, sum / d, cnt / d);
    }
    return 0;
}