Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2012-04-30SRM339 (Practice)

SRM 339 TestBettingStrategy

|  SRM 339 TestBettingStrategy - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM 339 TestBettingStrategy - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=7422

  • 簡単。
public class TestBettingStrategy {

	public double winProbability(int initSum, int goalSum, int rounds, int prob) {
		if (initSum >= goalSum) {
			return 1.0d;
		}
		
		int[] bets = new int[22];
		bets[0] = 1;
		for (int i = 1 ; i < 21 ; i++) {
			bets[i] = bets[i-1] * 2;
		}
		
		double p = prob * 1.0d / 100;
		double ans = 0.0d;
		double[][][] dp = new double[51][21][2002];
		dp[0][0][initSum] = 1.0d;
		for (int r = 0 ; r < rounds ; r++) {
			for (int l = 0 ; l < 21 ; l++) {
				for (int now = 0 ; now <= 2000 ; now++) {
					if (dp[r][l][now] > 0.0d) {
						double base = dp[r][l][now];
						int bet = bets[l];
						if (now < bet) {
							continue;
						}
						
						int win = (now - bet) + bet * 2;
						if (win >= goalSum) {
							win = 2001;
						}
						int lose = now - bet;
						
						if (win >= 2001) {
							ans += base * p;
						} else {
							dp[r+1][0][win] += base * p;
						}
						dp[r+1][Math.min(20, l+1)][lose] += base * (1.0d - p);
					}
				}
			}
		}
		return ans;
	}
}