URAL1936 Roshambo

08/06/2014

              一天不敲浮点数就调试跪成马系列……
             题意:输入一个n(<101) ,询问一场有n个人玩的猜拳游戏,若“每局赢的人留下、输的人退场、平局就继续”,那么期望经过多少局可以决出胜者,即只剩下最后一个人?
             硬要说的话……暴力推倒(导?)公式就好辣w。

F[i]    代表“剩下i个人时期望 f[i] 局能够决出胜者”。
M[i]  代表“含有 i 个人的回合 未平局时对期望的贡献为M[I]”。
P[i]    代表“含有 i 个人的回合 进行一次猜拳,平局(没有人被淘汰)的概率为P[i]”。
按照通常的思路,我们先考虑 F[i] 与 P[i]、M[i]的关系:
显然我们有:

{F[i]=M[i]*(1-P[i])+(M[i]+1)*(1-P[i])*P[i]+...+(M[i]+n)*(1-P[i])*P^n+...+(M[i]+{\infty})*(1-P[i])*P^{+\infty}}
通过高中的数列姿势,最终我们可以化简为:
{F[i]=M[i]+\frac{P[i]}{1-P[i]}}

然后,我们来考虑如何计算M[i]:

首先从三种获胜姿势中选出一种,其次再从 i 个人当中选出 j 个人获胜,此时对于期望的贡献为当前情况的概率乘以(F[j]+1),即为:
{M[i]=\sum_{j=1}^{i-1}\frac{3*C_{i}^{j}*(F[j]+1)}{3*(2^i-2)}}

↑感谢GLY学长的指正,样本空间的大小已经由\color{white}{2^i-2}更正为\color{white}{3*(2^i-2)}  ——Updated 2014/12/16

最后考虑P[i]:

设Q[i]为 i 个玩家进行一轮猜拳游戏有人被淘汰(未平局)的概率,则有:
{P[i]=1-Q[i]}

{Q[i]=\sum_{j=1}^{i-1}\frac{3*C_{i}^{j}}{3^i}}

{Q[i]=\frac{2^i-2}{3^{i-1}}}

 

用程序实现递推运算即可。

 

 

阿卡林哭一些关于这道题目不得不吐槽的事情……
C++的double精度实在是令人感动……人脑对拍了两个小时才敢交了过去,做好了加Eps的准备结果1Y,傲娇的评测姬一定不是按
照10^-6精度来评测的,大家试一下就知道了囧。
目测用Java来做是可以保证正确的,或许是因为C++党的愤怒导致放宽了评测标准……?