CodeForces#301 D.Bad Luck Island

~{→看不见LaTex格式的Dalao们请刷新本页Thanks♪(･ω･)ﾉ←}~

2019寒假集训题

E.Bad Luck Island

题面

The Bad Luck Island is inhabited by three kinds of species: $r$ rocks, $s$ scissors and $p$ papers. At some moments of time two random individuals meet (all pairs of individuals can meet equiprobably), and if they belong to different species, then one individual kills the other one: a rock kills scissors,scissors kill paper, and paper kills a rock. Your task is to determine for each species what is the probability that this species will be the only one to inhabit this island after a long enough period of time.

简要题意

在一个岛上，有 $𝑟 + 𝑠 + 𝑝$ 个人，其中有$𝑟$个人有石头，$𝑠$个人有剪刀，$𝑝$个人有布。遵循石头剪刀布的原则，输的人就狗带了。每两个人遇到概率的相等。
求每个人存活的概率。显然有同种东西的人存活概率相等，你只需要输出有石头，剪刀，布的人的存活概率即可。

Input

一行包括三个整数 $r,s,p$ ，如题意所示分别代表石头，剪刀，布。

Output

输出三个实数，由空格隔开，分别代表石头，剪刀，布存活的概率，如果输出与答案的误差不超过$10^{-9}$，则认为答案正确。

Sample Input 1

2 2 2

Sample Output 1

0.333333333333 0.333333333333 0.333333333333

Sample Input 2

2 1 2

Sample Output 2

0.150000000000 0.300000000000 0.550000000000

Sample Input 3

1 1 3

Sample Output 3

0.057142857143 0.657142857143 0.285714285714

Hint

$1\leq r,s,p\leq100$

不解释了吧？

一道期望$dp$，设$f[i][j][k]$，$i$为出石头的人，$j$为出剪刀的人，$k$为出布的人，组合一波即可。

初始状态为$f[r][s][p]=1$，转移方程见代码吧，基本相同。

Code

#include<bits/stdc++.h>
using namespace std;
int read()
{
	int x = 0, w = 0;
	char ch = 0;
	while (!isdigit(ch)) {w |= ch == '-'; ch = getchar();}
	while (isdigit(ch)) {x = (x << 3) + (x << 1) + ch - '0'; ch = getchar();}
	return w ? -x : x;
}
const int N = 110;
int r, s, p;
double f[N][N][N], A1, A2, A3;
long long calc(int x, int y, int z)
{
	return max(((x + y + z) * (x + y + z - 1) - x * (x - 1) - y * (y - 1) - z * (z - 1)) >> 1, 1);
}
int main()
{
	r = read(), s = read(), p = read();
	f[r][s][p] = 1;
	for (int i = r; ~i; --i)
		for (int j = s; ~j; --j)
			for (int k = p; ~k; --k)
			{
				if (!i && !j && !k) continue;
				if (i == r && j == s && k == p) continue;
				f[i][j][k] += f[i + 1][j][k] * (1.0 * (i + 1) * k / calc(i + 1, j, k));
				f[i][j][k] += f[i][j + 1][k] * (1.0 * (j + 1) * i / calc(i, j + 1, k));
				f[i][j][k] += f[i][j][k + 1] * (1.0 * (k + 1) * j / calc(i, j, k + 1));
			}
	for (int i = 1; i <= r; ++i) A1 += f[i][0][0];
	for (int i = 1; i <= s; ++i) A2 += f[0][i][0];
	for (int i = 1; i <= p; ++i) A3 += f[0][0][i];
	printf("%.11lf %.11lf %.11lf", A1, A2, A3);
	return 0;
}