URAL 1936 Roshambo（求期望）

Description

Bootstrap: Wondering how it's played? Will: It's a game of deception. But your bet includes all the dice, not just your own. What are they wagering? Bootstrap: Oh, the only thing we have. Years of service. Will: So any crew member can be challenged? Bootstrap: Aye. Anyone. Will: I challenge Davy Jones.

All that the pirates have on the Flying Dutchman is the years of service that are left for them. Every crewman wants to shorten it. That is why gambling is very popular on the ship, the winner have a chance to shorten his years of service significantly.

Pirates often gather to play “Roshambo”, also known as “rock-scissors-paper”. The game consists of several sets. In the beginning of each set players stand in a circle, count to three and show one of three gestures simultaneously, conventionally called as rock, scissors and paper. If everyone shows the same gesture or if each of the three gestures is shown, then nobody leave the game and they play another set. If among the shown gestures there are only two different then only players that chose the victorious gesture play the next set. Scissors beats rock, rock beats paper and paper beats scissors. The game continues until the only one player is left, and that pirate is called the winner. The winner’s time of service is shortened on the number of years that equals the number of the sets played, while the losers get extra years.

Bootstrap Bill decided to try his fortune. You should help him determine the expected value of prize in case of his victory. Pirates don’t know any complicated strategies for this game. So you can suppose that pirates show every gesture equiprobably.

Input

The only line contains integer n that is the number of sailors that are going to play, including Bill (2 ≤ n ≤ 100).

Output

Output the expected amount of years that will be taken off from winner. Absolute or relative error should be no more than 10⁻⁶.

题目大意：n个人玩石头剪刀布（一起上的），每一round若平局则继续，否则输的出局，赢的留下来，进入下一round。直到剩下一个人，问期望进行多少round。

思路：递推。令dp[n]代表n个人的期望结束盘数（也就是我们要的答案）。

令ret代表n个人，这一场不平手的结束盘数。枚举赢的人数 i ，那么赢的人数为 i 的概率 p 为从 n 个人里面选 i 个人赢，其中这 i 个人的选择有3种，这 i 个人都出前面选的那一种，概率为 (1/3)^i ，剩下的n-i个人，都选被前面选的那种打败的一种，概率为 (1/3)^(n-i)。然后赢了之后，就是剩下 i 个人，也就是 i 个人结束游戏的期望盘数dp[i] + 1，符合递推条件。

令q为平局的概率，这个很容易求，q = 1 - sum{p}，p就是前面的所有非平局的概率。

ret = sum{(dp[i]+1) * c[n][i] * 3 * (1/3)^i * (1/3)^(n-i)} = sum{(dp[i]+1) * c[n][i] * (1/3)^(i-1)}

那么dp[n] = (1-q)*ret + q*(1-q)*(1+ret) + q^2*(1-q)*(2+ret) + q^3*(1-q)*(3+ret) + ……

//提取出1-q

=(1-q)(ret + (1+ret)*q + (2+ret)*q^2 + (3+ret)*q^3 + ……)

//把ret提出来，分别求极限

=(1-q)(ret/(1-q) + q/(1-q)^2)

=ret + q/(1-q)

然后一切就好办了。

PS：代码被我各种合并已经跟前面讲的大不一样了……

PS2：前面写得好乱不知道有没有写错的啊……

PS3：代码中的q是上面的1-q，也就是sum{p}，因为不改成这样会出现精度误差导致无法AC。具体原因我想了一下，比如q原来是1，当q减去一个很小的数的时候，破了double的精度，那么q还是1，然后这个数就被丢掉了，造成了误差。

代码（31MS）（递推会快一点的……）：

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <iostream>
 4 #include <algorithm>
 5 #include <queue>
 6 #include <cmath>
 7 #include <iomanip>
 8 using namespace std;
 9 typedef long long LL;
10 
11 const int MAXN = 110;
12 const double EPS = 1e-12;
13 
14 double dp[MAXN];
15 double c[MAXN][MAXN];
16 
17 double C(int n, int m) {
18     if(c[n][m] > EPS) return c[n][m];
19     if(n == m) return c[n][m] = 1;
20     if(m == 1) return c[n][m] = n;
21     return c[n][m] = C(n - 1, m - 1) + C(n - 1, m);
22 }
23 
24 double solve(int n) {
25     if(n == 1) return 0;
26     if(dp[n] > EPS) return dp[n];
27     double ret = 0, q = 0;
28     for(int i = 1; i < n; ++i) {
29         double p = C(n, i) * pow(1./3, n - 1);
30         ret += p * (solve(i));
31         q += p;
32     }
33     return dp[n] = (ret + 1) / (q);
34 }
35 
36 int main() {
37     int n;
38     while(scanf("%d", &n) != EOF) {
39         cout.precision(10);
40         cout<<setiosflags(ios::fixed)<<solve(n)<<endl;
41     }
42 }

View Code