LightOj_1027 A Dangerous Maze

时间:2023-03-09 04:20:08
LightOj_1027  A Dangerous Maze

题目链接

题意:

  你在一个迷宫里, 开始的时候你面前有n个门, 选择每个门的概率相等, 有两种结果:

  1)回到|x|分钟之前(x为负时)

  2)x分钟之后出迷宫(x为正时)

  每次回到|x|分钟之前, 你都记不得你曾经选过哪扇门

  问走出迷宫所用时间的期望。

思路:

  因为每次都不记得曾经的选择, 所以每次的期望都是一样的。

  设,T1为每次走出去所用时间的期望, T2为回到之前所用时间的期望。

  则E = p * T1 + (T2 + E) * (1 - p)

  化简后得, p * E = p * T1 + T2 * (1 - p)

  假设有m个门是走出去的, 则p = m / n

  代进上式得:m * E / n = m * T1 / n + (n - m) * T2 / n

          m * E = m * T1 + (n - m) * T2

  T1 = (sigma x[i]) / m, x[i] > 0, T2 = (sigma |x[i]|) / (n - m), x[i] < 0

  E = (sigma x[i] + sigma |x[i]|) / m

代码:

  

 #include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <ctime>
#include <set>
#include <map>
#include <list>
#include <queue>
#include <string>
#include <vector>
#include <fstream>
#include <iterator>
#include <iostream>
#include <algorithm>
using namespace std;
#define LL long long
#define MAXN 110
#define MOD 1000000007
#define eps 1e-6
int n;
int t[], m;
int gcd(int a, int b)
{
return b == ? a : gcd(b, a % b);
} int main()
{
int T;
int kcase = ;
scanf("%d", &T);
while(T --)
{
scanf("%d", &n);
m = ;
t[] = t[] = ;
for(int i = ; i < n; i ++)
{
int x;
scanf("%d", &x);
if(x > )
{
t[] += x;
m ++;
}
else
t[] += (- * x);
}
if(!m) printf("Case %d: inf\n", ++ kcase);
else
{
int k = gcd(t[] + t[], m);
printf("Case %d: %d/%d\n", ++ kcase, (t[] + t[]) / k, m / k);
}
}
return ;
}