POJ 2651

So you want to be a 2n-aire?

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 507		Accepted: 323

Description

The player starts with a prize of $1, and is asked a sequence of n questions. For each question, he may 

• quit and keep his prize. 
• answer the question. If wrong, he quits with nothing. If correct, the prize is doubled, and he continues with the next question.

After the last question, he quits with his prize. The player wants to maximize his expected prize. 
Once each question is asked, the player is able to assess the probability p that he will be able to answer it. For each question, we assume that p is a random variable uniformly distributed over the range t .. 1.

Input

Input is a number of lines, each with two numbers: an integer 1 <= n <= 30, and a real 0 <= t <= 1. Input is terminated by a line containing 0 0. This line should not be processed.

Output

For each input n and t, print the player's expected prize, if he plays the best strategy. Output should be rounded to three fractional digits.

Sample Input

1 0.5
1 0.3
2 0.6
24 0.25
0 0

Sample Output

1.500
1.357
2.560
230.138

Source

Waterloo local 2005.09.17

#include<iostream>
#include<stdio.h>
#include<iostream>
#include<cmath>
#include<math.h>
#include<queue>
#include<set>
#include<map>
#include<iomanip>
#include<algorithm>
#include<stack>
#define inf 0x3f3f3f3f
using namespace std;
typedef long long ll;
double t;int n;
double ans;
ll mypow(int a,int b)
{
    ll res=1;
    while(b--)res*=a;
    return res;
}
double f[33];
int main()
{
#ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
#endif // ONLIN
    double p0,p1;
    while(cin>>n>>t)
    {
        if(n==0)break;
        f[n]=1.0*mypow(2,n);
        for(int i=n-1;i>=0;i--)
        {
            p0=max(t,1.0*mypow(2,i)/f[i+1]);
            p1=(p0-t)/(1-t);
            f[i]=mypow(2,i)*p1+(1+p0)/2*f[i+1]*(1-p1);
        }
        printf("%.3f\n",f[0]);
    }
}