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 ith door, it can either take you back to the same position where you begun in xi minutes, or can take you out of the maze after xi 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.

链接🔗

「LightOJ 1027」A Dangerous Maze

题解

设 sum1 为直接逃出的期望时间，则 sum1=∑ai∗1nsum1 = \sum a_i * \frac{1}{n},aia_i 表示成功逃离所需时间，frac1nfrac{1}{n} 表示选中该门的概率
同理，设 sum2 为返回起点的期望时间，sum2=∑bi∗1nsum2 = \sum b_i * \frac{1}{n}
我们设 逃出的期望为 E，从起点逃离出去的期望为 $ 1 / n * E $ , 则逃出的期望等于直接逃出期望+返回起点后逃出期望，返回起点后逃出期望为返回起点的期望,因为有door2个门会使我们返回起点，所以还要在逃离出去期望上乘上door2

代码

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxd = 105;
int arr[maxd],n;
int gcd(int x,int y)
{
    if(!y) return x;
    return gcd(y,x%y);
}
int main()
{
    // freopen("a.in","r",stdin);
    // freopen("k.out","w",stdout);
    int t,tot = 0;scanf("%d",&t); 
    while(t--)
    {
        scanf("%d",&n);
        int sum1=0,sum2=0,door=0;
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&arr[i]);
            if(arr[i] < 0) door++,sum2 += -arr[i];
            else sum1 += arr[i];     
        }
        int E1 = sum1 + sum2;
        int E2 = n - door;

        if(!E2) printf("Case %d: inf\n",++tot);
        else
        {
            int d = gcd(E1,E2);
            printf("Case %d: %d/%d\n",++tot,E1/d,E2/d);
        }
    }
    return 0;
}