You have been invited to the popular TV show "Would you like to be a millionaire?". Of course you would!
The rules of the show are simple:
Each of the following N lines has the format "M P X", where:
double d[16][(1<<15)+1];
double solve()
{
int m;
double p, x;
cin >> m >> p >> x;
if (x >= MAX) return 1.0;
if (x < 1.0/(1<<m)) return 0.0;
d[0][1] = 1.0;
for (int j = 1; j <= m; j++)
{
d[j][1<<j] = 1.0;
for (int i = 1; i < (1<<j); i++)
{
double c = 0.0;
for (int k = (i+1)/2; k <= (1<<(j-1)); k++)
{
if (i-k >= 0)
{
double t = p*d[j-1][k] + (1-p)*d[j-1][i-k];
if (t > c) c = t;
}
}
d[j][i] = c;
}
}
return d[m][(int)((1<<m)*(x/MAX))];
}
int main()
{
int cases;
cin >> cases;
for (int i = 1; i <= cases; i++)
{
printf("Case #%d: %0.6f\n", i, solve());
}
return 0;
}
Read full article from Dashboard - APAC Semifinal 2008 - Google Code Jam
The rules of the show are simple:
- Before the game starts, the host spins a wheel of fortune to determine P, the probability of winning each bet.
- You start out with some money: X dollars.
- There are M rounds of betting. In each round, you can bet any part of your current money, including none of it or all of it. The amount is not limited to whole dollars or whole cents. If you win the bet, your total amount of money increases by the amount you bet. Otherwise, your amount of money decreases by the amount you bet.
- After all the rounds of betting are done, you get to keep your winnings (this time the amount is rounded down to whole dollars) only if you have accumulated $1000000 or more. Otherwise you get nothing.
Input
The first line of input gives the number of cases, N.Each of the following N lines has the format "M P X", where:
- M is an integer, the number of rounds of betting.
- P is a real number, the probability of winning each round.
- X is an integer, the starting number of dollars.
double d[16][(1<<15)+1];
double solve()
{
int m;
double p, x;
cin >> m >> p >> x;
if (x >= MAX) return 1.0;
if (x < 1.0/(1<<m)) return 0.0;
d[0][1] = 1.0;
for (int j = 1; j <= m; j++)
{
d[j][1<<j] = 1.0;
for (int i = 1; i < (1<<j); i++)
{
double c = 0.0;
for (int k = (i+1)/2; k <= (1<<(j-1)); k++)
{
if (i-k >= 0)
{
double t = p*d[j-1][k] + (1-p)*d[j-1][i-k];
if (t > c) c = t;
}
}
d[j][i] = c;
}
}
return d[m][(int)((1<<m)*(x/MAX))];
}
int main()
{
int cases;
cin >> cases;
for (int i = 1; i <= cases; i++)
{
printf("Case #%d: %0.6f\n", i, solve());
}
return 0;
}
Read full article from Dashboard - APAC Semifinal 2008 - Google Code Jam
