此文章可以使用目录功能哟↑(点击上方[+])
Light OJ 1027 - A Dangerous Maze
Accept: 0 Submit: 0
Time Limit: 2 second(s) Memory Limit: 32MB
Problem Description
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.
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 ith integer (xi) is positive, you can assume that the ith door will take you out of maze after xi minutes. If it's negative, then the ith door will take you back to the beginning position after abs(xi) minutes. You can safely assume that 1 ≤ abs(xi) ≤ 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
1
1
2
-10 -3
3
3 -6 -9
Sample Output
Case 2: inf
Case 3: 18/1
Problem Idea
解题思路:
【题意】
迷宫当前位置有n扇门,你需要选择一扇门打开
如果打开的第i扇门的Xi值为正,则经过Xi时间后你可以离开迷宫;
如果Xi是负数的话,那么你将在-Xi时间后回到起点,即门前,并且你不记得之前选过哪扇门
你对每扇门的选择是等可能性的,问你离开迷宫的期望时间
【类型】
求期望
【分析】
首先,我们先假设一些变量
令离开迷宫的期望时间为E,选择到Xi是正数的概率为P1,选择到Xi是负数的概率为P2,然后选择了正数后平均在T1时间后离开迷宫,选择了负数后平均在T2时间后回到起点
因为选到正数就可以离开,故一次性离开的期望时间为P1*T1
若选到了负数,那我回到起点的期望时间为P2*T2
回到起点之后,因为我不记得之前选了哪扇门,所以此时状态其实和刚开始的状态一致,除了多花费了回到起点的期望时间
所以此时离开迷宫的期望时间还是E
故可得期望公式E=P1*T1+P2*(T2+E),化简后为
因为结果最后要输出最简分数,所以式子需进一步化简
令Xi为正数的次数为k,所有为正数的Xi之和为sum1,所有为负数的Xi之和为sum2
那么可得,
代入上式化简
当k=0时,不可能离开迷宫,输出"inf"
【时间复杂度&&优化】
O(nT)
题目链接→Light OJ 1027 - A Dangerous Maze
Source Code
/*Sherlock and Watson and Adler*/
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<queue>
#include<stack>
#include<math.h>
#include<vector>
#include<map>
#include<set>
#include<cmath>
#include<complex>
#include<string>
#include<algorithm>
#include<iostream>
#define eps 1e-8
#define LL long long
#define bitnum(a) __builtin_popcount(a)
using namespace std;
const int N = 105;
const int M = 16;
const int inf = 1000000007;
const int mod = 1000000007;
int gcd(int a,int b)
{if(a%b)return gcd(b,a%b);return b;
}
int main()
{int t,n,p=1,i,x,k,sum1,sum2,numerator,denominator;scanf("%d",&t);while(t--){sum1=sum2=k=0;scanf("%d",&n);for(i=0;i<n;i++){scanf("%d",&x);if(x>0)k++,sum1+=x;elsesum2-=x;}numerator=sum1+sum2;denominator=k;printf("Case %d: ",p++);if(!k)puts("inf");else{k=gcd(numerator,denominator);printf("%d/%d\n",numerator/k,denominator/k);}}return 0;
}