分析
首先可以发现,不到最后是不会选择猜的。
假设你问了一张牌,对手没有,那么对手就会怀疑这张牌是桌上那张。
考虑这样一种神奇的操作:询问一张自己手上有的牌。这样子对手就会怀疑这张牌是桌上的,然后如果他问了他就输了。我们把这种操作称为欺骗。
考虑 DP 。设 $f_{n,m}$ 表示先手有 $n$ 张牌、后手有 $m$ 张牌时,先手的获胜概率。
我们列一个表格,表示在先手如何操作后手如何操作时先手的获胜概率:
先手$\backslash$后手 | 猜测 | 欺骗 |
---|---|---|
猜测 | $\frac{m}{m+1}(1-f_{m-1,n})$ | $\frac{1}{m+1}+\frac{m}{m+1}(1-f_{m-1,n})$ |
欺骗 | $1$ | $1-f_{m,n-1}$ |
为了方便,设 $A=\frac{m}{m+1}(1-f_{m-1,n})$ ,$B=1$ ,$C=\frac{1}{m+1}+\frac{m}{m+1}(1-f_{m-1,n})$ ,$D=1-f_{m,n-1}$ 。
双方都会走最优策略,所以会达成混合策略纳什均衡。
假设先手猜测的概率是 $p$ ,欺骗的概率是 $1-p$ ,那么可以解得 $p=\frac{D-B}{A-B-C+D}$ 。
具体解的过程是这样子的:
$$
\begin{aligned}
pA+(1-p)B&=pC+(1-p)D\\
pA+B-pB&=pC+D-pD\\
(A-B-C+D)p&=D-B\\
p&=\frac{D-B}{A-B-C+D}
\end{aligned}
$$
然后就可以直接转移了。
DP 的边界是 $f_{0,m}=\frac{1}{m+1},f_{n,0}=1$ 。
代码
// ===================================
// author: M_sea
// website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;
inline int read() {
int X=0,w=1; char c=getchar();
while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
return X*w;
}
const int N=1000+10;
int n,m;
double dp[N][N];
inline double dfs(int n,int m) {
if (!n) return 1.0/(m+1);
if (!m) return 1.0;
if (dp[n][m]) return dp[n][m];
double A=1.0*m/(m+1)*(1.0-dfs(m-1,n)),B=1.0;
double C=1.0/(m+1)+A,D=1.0-dfs(m,n-1);
double P=(D-B)/(A-B-C+D);
return dp[n][m]=P*A+(1-P)*B;
}
int main() {
n=read(),m=read();
printf("%.10lf %.10lf\n",dfs(n,m),1-dfs(n,m));
return 0;
}