LightOJ-1027-A Dangerous Maze(概率)
2024-10-07 01:42:59
链接:
https://vjudge.net/problem/LightOJ-1027#author=634579757
题意:
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.
思路:
考虑当x大于0则出去的期望时间为1/nt,如果小于0出去的期望时间为1/n(t+d).其中d为整体出去的期望时间。
推出d = 1/nsumt+ne/nd.其中sumt为总时间及abs(t)的和。ne为负值的们。
代码:
#include <iostream>
#include <memory.h>
#include <string>
#include <istream>
#include <sstream>
#include <vector>
#include <stack>
#include <algorithm>
#include <map>
#include <queue>
#include <math.h>
#include <cstdio>
#include <set>
#include <iterator>
#include <cstring>
#include <assert.h>
using namespace std;
typedef long long LL;
int n;
int main()
{
int t, cnt = 0;
scanf("%d",&t);
while (t--)
{
scanf("%d", &n);
int sum = 0, ne = 0, v;
bool flag = false;
for (int i = 1;i <= n;i++)
{
scanf("%d", &v);
if (v > 0)
flag = true;
if (v < 0)
ne++;
sum += abs(v);
}
if (!flag)
printf("Case %d: inf\n", ++cnt);
else
printf("Case %d: %d/%d\n", ++cnt, sum/__gcd(sum, n-ne), (n-ne)/__gcd(sum, n-ne));
}
return 0;
}
最新文章
- BZOJ‘s Usaco 奶牛题集锦
- navicat 结合快捷键
- JMeter--一、安装JMeter
- 分享下对JAVA程序员成长之路的总结<;转>;
- GitHub的.gitignore文件设置
- input输入样式,动画
- Hibernate的延迟加载
- <;script>;标签应该放到<;/body>;标签之前
- C语言 文件操作3--文件重定向与扫描
- Android扫描文件
- 【转】在delphi中实现控件的拖拽
- oc对象的内存管理
- 面试题之redis实现限制1小时内每用户Id最多只能登录5次
- JavaScript兼容问题汇总[实时更新]
- SGU 202 The Towers of Hanoi Revisited (DP+递归)
- win10 uwp 如何让WebView标识win10手机
- LeetCode 34. Search for a Range (找到一个范围)
- localStorage用法总结
- goodbye 2018, hello 2019
- 32位二进制IP地址与十进制IP地址互相转换