Codeforces Round #301 (Div. 二) D（概率dp）

Codeforces Round #301 (Div. 2) D（概率dp）

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

The single line contains three integers r, s and p (1 ≤ r, s, p ≤ 100) — the original number of individuals in the species of rock, scissors and paper, respectively.

Output

Print three space-separated real numbers: the probabilities, at which the rocks, the scissors and the paper will be the only surviving species, respectively. The answer will be considered correct if the relative or absolute error of each number doesn't exceed 10 - 9.

Sample test(s)

input
2 2 2

output
0.333333333333 0.333333333333 0.333333333333

input
2 1 2

output
0.150000000000 0.300000000000 0.550000000000

input
1 1 3

output
0.057142857143 0.657142857143 0.285714285714

题意：石头剪刀布游戏，给你r个石头，s个剪刀，p个布，问你最后只剩下单个种类的概率分别是多少；

思路：很简单的概率dp，用dp[r][s][p] 表示还剩下r个石头，s个剪刀，p个布的概率，那么最终我们只要分别累加 dp[r][0][0]，dp[[0][s][0]，dp[0][0][p]就OK啦！

代码如下：

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 105;
double dp[N][N][N];
int r, s, p;

int main()
{
	while(~scanf("%d%d%d", &r, &s, &p))
	{
		memset(dp, 0, sizeof(dp));
		dp[r][s][p] = 1;
		for(int i = r; i >= 0; i--)
		{
			for(int j = s; j >= 0; j--)
			{
				for(int k = p; k >= 0; k--)
				{
					if(!i && !j || !i && !k || !j && !k) continue;
					double ans = dp[i][j][k];
					double tmp = i*j + i*k + j*k;
					if(i) dp[i-1][j][k] += ans*double(i*k)/tmp;
					if(j) dp[i][j-1][k] += ans*double(i*j)/tmp;
					if(k) dp[i][j][k-1] += ans*double(j*k)/tmp;
				}
			}
		}
		double a = 0, b = 0, c = 0;
		for(int i = 1; i <= r; i++) a += dp[i][0][0];
		for(int j = 1; j <= s; j++) b += dp[0][j][0];
		for(int k = 1; k <= p; k++) c += dp[0][0][k];
		printf("%.9lf %.9lf %.9lf\n", a, b, c);
	}
	return 0;
}

Codeforces Round #301 (Div. 二) D（概率dp）

相关推荐