當前位置：首頁 > 编程资源 > 编程问答 >内容正文

编程问答

CodeForces - 540D Bad Luck Island —— 求概率

發布時間：2023/12/20 编程问答 37 豆豆

生活随笔收集整理的這篇文章主要介紹了 CodeForces - 540D Bad Luck Island —— 求概率小編覺得挺不錯的,現在分享給大家,幫大家做個參考.

題目鏈接：https://vjudge.net/contest/226823#problem/D

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.

Examples

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個布。每次都隨機挑出，問：最后只剩下石頭、剪刀、布的概率分別是多少？

題解：

1.設dp[i][j][k]為：剩余i個石頭，j個剪刀，k個布的概率。

2.可知：如果選到的兩個是同類型，那么這一輪是無意義的，且對結果毫無影響，所以可忽略這種情況，只需考慮兩者不同的情況。

3.假設當前還剩余i個石頭，j個剪刀，k個布，那么下一輪抽到石頭和剪刀的概率為（不需考慮同類型的）：(i*j)/(i*j+i*k+j*k)，而此種情況的結果為[i][j-1][k]，所以dp[i][j-1][k] +=?(i*j)/(i*j+i*k+j*k)*dp[i][j][k]。同理剩下的兩種情況。

代碼如下：

1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cmath> 5 #include <cstdlib> 6 #include <string> 7 #include <vector> 8 #include <map> 9 #include <set> 10 #include <queue> 11 #include <sstream> 12 #include <algorithm> 13 using namespace std; 14 typedef long long LL; 15 const double eps = 1e-8; 16 const int INF = 2e9; 17 const LL LNF = 9e18; 18 const int MOD = 1e9+7; 19 const int MAXN = 1e2+10; 20 21 double dp[MAXN][MAXN][MAXN]; 22 int main() 23 { 24 int n, m, p; 25 while(scanf("%d%d%d",&n,&m,&p)!=EOF) 26 { 27 memset(dp, 0, sizeof(dp)); 28 dp[n][m][p] = 1.0; 29 for(int i = n; i>=0; i--) 30 for(int j = m; j>=0; j--) 31 for(int k = p; k>=0; k--) 32 { 33 if(i&&j) dp[i][j-1][k] += (1.0*i*j/(i*j+j*k+i*k))*dp[i][j][k]; 34 if(j&&k) dp[i][j][k-1] += (1.0*j*k/(i*j+j*k+i*k))*dp[i][j][k]; 35 if(i&&k) dp[i-1][j][k] += (1.0*i*k/(i*j+j*k+i*k))*dp[i][j][k]; 36 } 37 38 double r1 = 0, r2 = 0, r3 = 0; 39 for(int i = 1; i<=n; i++) r1 += dp[i][0][0]; 40 for(int i = 1; i<=m; i++) r2 += dp[0][i][0]; 41 for(int i = 1; i<=p; i++) r3 += dp[0][0][i]; 42 43 printf("%.10f %.10f %.10f\n", r1,r2,r3); 44 } 45 } View Code

轉載于:https://www.cnblogs.com/DOLFAMINGO/p/8995363.html

總結

以上是生活随笔為你收集整理的CodeForces - 540D Bad Luck Island —— 求概率的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。