codeforces 148D Bag of mice (概率)

r囧r小猫 2022-06-04 06:48 120阅读 0赞

The dragon and the princess are arguing about what to do on the New Year's Eve. The dragon suggests flying to the mountains to watch fairies dancing in the moonlight, while the princess thinks they should just go to bed early. They are desperate to come to an amicable agreement, so they decide to leave this up to chance.

They take turns drawing a mouse from a bag which initially contains *w* white and *b* black mice. The person who is the first to draw a white mouse wins. After each mouse drawn by the dragon the rest of mice in the bag panic, and one of them jumps out of the bag itself (the princess draws her mice carefully and doesn't scare other mice). Princess draws first. What is the probability of the princess winning?

If there are no more mice in the bag and nobody has drawn a white mouse, the dragon wins. Mice which jump out of the bag themselves are not considered to be drawn (do not define the winner). Once a mouse has left the bag, it never returns to it. Every mouse is drawn from the bag with the same probability as every other one, and every mouse jumps out of the bag with the same probability as every other one.

Input

The only line of input data contains two integers *w* and *b* (0 ≤ *w*, *b* ≤ 1000).

Output

Output the probability of the princess winning. The answer is considered to be correct if its absolute or relative error does not exceed 10 - 9.

Example

Input

1 3

Output

0.500000000

Input

5 5

Output

0.658730159

Note

Let's go through the first sample. The probability of the princess drawing a white mouse on her first turn and winning right away is 1/4. The probability of the dragon drawing a black mouse and not winning on his first turn is 3/4 \* 2/3 = 1/2. After this there are two mice left in the bag — one black and one white; one of them jumps out, and the other is drawn by the princess on her second turn. If the princess' mouse is white, she wins (probability is 1/2 \* 1/2 = 1/4), otherwise nobody gets the white mouse, so according to the rule the dragon wins.

题意：在一个包里有许多黑色的老鼠和许多白色的老鼠，龙和公主轮流从包中取出一只老鼠，谁先取出白鼠谁嬴，龙每次取出老鼠的时候会惊吓到其他老鼠，随机一只老鼠会从包里跳出来，不会再回去，而公主取老鼠的时候不会惊吓到他们，取每一个老鼠的概率是一样的，每一个老师被惊吓的概率也是一样的，当包里没有白鼠的时候算龙赢。现在告诉你包里有w个白鼠和b个黑鼠，公主先取，问公主赢的概率。

思路：很多人都是用概率DP做的，但是我DP特别不熟练= =，于是我在训练赛的时候想到了另一种方法。写两个函数互相递归调用。第一个函数返回的是公主在当前局面先手获胜的概率，第二个函数返回的是龙在当前局面抽到黑鼠并且公主在之后会获胜的概率。第一个函数的返回值等于公主当前回合抽白鼠的概率+调用第二个函数，而第二个函数的返回值等于龙在当前回合抽黑鼠的概率+调用第一个函数。这样子互相递归下去最后其实和概率DP是差不多的，也算是一种递推关系吧。然后要用记忆化搜索优化一下。详细的看代码吧。

AC代码：

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <string>
    #include <cstdlib>
    #include <cmath>
    #include <vector>
    #include <queue>
    #include <map>
    #include <algorithm>
    #include <set>
    #include <functional>
    using namespace std;
    typedef long long LL;
    typedef unsigned long long ULL;
    const int INF = 1e9 + 5;
    const int MAXN = 1005;
    const int MOD = 1e9 + 7;
    const double eps = 1e-9;
    const double PI = acos(-1.0);
    LL gcd(LL a, LL b) { return b == 0 ? a : gcd(b, a%b); }
    LL ppow(LL a, LL b) { LL res = 1; for (int i = 1; i <= b; i++)	res *= a; return res; }
    LL quick_mod(LL a, LL b, LL c) { LL ans = 1; while (b) { if (b % 2 == 1)ans = (ans*a) % c; b /= 2; a = (a*a) % c; }return ans; }
    
    double drdp[1005][1005];
    double prdp[1005][1005];
    
    void init()
    {
    	memset(drdp, -1, sizeof drdp);
    	memset(prdp, -1, sizeof prdp);
    }
    
    double drB(int W, int B);
    
    double prW(int W, int B)
    {
    	if (fabs(prdp[W][B] + 1)>eps)return prdp[W][B];//记忆化搜索
    	if (W <= 0)return 0;//没有白鼠公主就输了
    	double w = W;
    	double b = B;
    	return prdp[W][B] = w / (w + b) + b / (w + b)*drB(W, B - 1);
    }
    
    double drB(int W, int B)
    {
    	double ans;
    	if (fabs(drdp[W][B] + 1)>eps)return drdp[W][B];//记忆化搜索
    	if (B <= 0)return 0;//没有黑鼠龙一定拿白鼠，公主就输了
    	double w = W;
    	double b = B;
    	if (B >= 2 && W >= 1)//当前状态既有可能吓跑黑鼠也有可能吓跑白鼠
    		ans = b / (w + b)*(b - 1) / (w + b - 1)*prW(W, B - 2) + b / (w + b)*w / (w + b - 1)*prW(W - 1, B - 1);
    	else if (B < 2 && W >= 1)//当前状态只能吓跑白鼠
    		ans = b / (w + b)*w / (w + b - 1)*prW(W - 1, B - 1);
    	else//当前状态只能吓跑黑鼠，也就是说没白鼠了，那么公主一定输了
    		ans = 0;
    	return drdp[W][B] = ans;
    }
    
    int main()
    {
    	int W, B;
    	while (scanf("%d%d", &W, &B) != EOF)
    	{
    		init();
    		printf("%.9lf\n", prW(W, B));
    	}
    }