lightoj 1050 - Marbles - dblank

lightoj 1050 - Marbles

Your friend Jim has challenged you to a game. He has a bag containing red and blue marbles. There will be an odd number of marbles in the bag, and you go first. On your turn, you reach into the bag and remove a random marble from the bag; each marble may be selected with equal probability. After your turn is over, Jim will reach into the bag and remove a blue marble; if there is no blue marble for Jim to remove, then he wins. If the final marble removed from the bag is blue (by you or Jim), you will win. Otherwise, Jim wins.

Given the number of red and blue marbles in the bag, determine the probability that you win the game.

Input starts with an integer T (≤ 10000), denoting the number of test cases.

Each case begins with two integers R and B denoting the number of red and blue marbles respectively. You can assume that 0 ≤ R, B ≤ 500 and R+B is odd.

For each case of input you have to print the case number and your winning probability. Errors less than 10-6 will be ignored.

Sample Input

1 2

2 3

2 5

11 6

4 11

Output for Sample Input
Case 1: 0.3333333333

Case 2: 0.13333333

Case 3: 0.2285714286

Case 4: 0

Case 5: 0.1218337218

思路:因为(r+b)是奇数,所以最后一个球一定是先手摸的,这个时候保证这个球是蓝球就获胜,我们可以反着推导,(0, 1)是赢得必然条件,于是用dpi表示i个蓝球j个红球的获胜概率,让dp0=1,因为这是胜利的必然结果状态,对于一轮,要么(r, b), 要么(b, b),于是对于dpi,有dpi = dpi-1 i/(i+j) + dpij/(i+j) 。dp0是怎么都是赢,于是所有的dp0=1,直接把表打好。

using namespace std;
const double eps = 1e-10;
const int inf = 0x3f3f3f3f, N = 1e5 + 10, Mod = 998244353;
typedef long long ll;
using namespace std;
double dp550;
int main()
    int t;
    memset(dp, 0, sizeof(dp));
    dp0 = 1;
    for(int i = 1; i<=500; i++)
        for(int j = 1; j<=500; j++)
            dp0 = 1;
            dpi = dpi-11.0i/(i+j);
    for(int cas = 1; cas <= t; cas++)
        int r, b;
        scanf("%d%d", &r, &b);
        printf("Case %d: ", cas);
        printf("%.10fn", dpr);
    return 0;