SRM339-D1-500

#define ll long long
#include <bits/stdc++.h>
using namespace std;

const int OO = 1e9;
const double EPS = 1e-9;

class TestBettingStrategy {
public:
    int goal;
    double p;
    double mem[1001][51][11];
    double solve(int money, int rounds, int cb) {
        int bet = (1 << cb);
        if(money >= goal) {
            return 1;
        }
        if(rounds == 0 || bet > money) {
            return 0;
        }
        if(mem[money][rounds][cb] != -1) {
            return mem[money][rounds][cb];
        }
        double &ret = mem[money][rounds][cb];
        ret = p*solve(min(1000,money+bet),rounds-1,0) + (1-p)*solve(max(0,money-bet),rounds-1,cb+1);
        return ret;

    }

    double winProbability(int initSum, int goalSum, int rounds, int prob) {
        goal = goalSum;
        p = prob/100.0;
        for(int i = 0; i <= 1000; i++) {
            for(int j = 0; j <= rounds; j++) {
                for(int k = 0; k <= 10; k++) {
                    mem[i][j][k] = -1;
                }
            }
        }
        return solve(initSum, rounds, 0);
    }
};