1577. So you want to be a 2^n-aire?
The player starts with a prize of $1 and is
asked a sequence of n questions. For each question, he may
·
quit a
game 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 can
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. Each line is a separate test case with two numbers: an
integer n (1 ≤ n ≤ 30) and a real t (0 ≤ t ≤ 1). Input is terminated by a line containing two zeroes.
This line should not be processed.
Output. For each test case print the player’s expected prize
if he plays the best strategy. Output should be rounded to three fractional
digits.
|
Sample
input |
Sample
output |
|
1 0.5 1 0.3 2 0.6 24 0.25 0 0 |
1.500 1.357 2.560 230.138 |
SOLUTION
probability theory
Algorithm analysis
Let f(n, a) be the maximum possible prize if the player
is asked n questions and the initial sum is a. If n = 0,
then the player is left with the initial sum, that is, f(0, a) = a.
The probability
of a correct answer is equal to p, t ≤ p ≤ 1. If the player answers the
first question correctly, then he has to answer n – 1 questions with a prize amount of 2a.
With a probability of 1 – p, the wrong answer is given, and the money
disappears. That is, the expected
amount of winnings after the first answer will be equal to
p * f(n –
1, 2a) + (1 – p) * 0 = p * f(n – 1, 2a)
If this value is
greater than the previous sum a, then it is worth answering the
question, otherwise the game should be stopped. The expected payoff after
answering the question is max(a, p * f(n – 1, 2a)).
Since the probability p is uniformly distributed on the interval [t
.. 1], then
f(n, a)
= 
If t = 1,
then the probability of giving the correct answer is 1, and in this case, all n
questions should be answered, while receiving a payoff of 2n.
Example
Consider the
third test
case, n = 2, t = 0.6. The initial capital is a = 1.
f(2, 1) = 
, f(1, 2) =
, f(0, 4) = 4
Compute the value of f(1, 2) in terms of f(0, 4):
f(1, 2) = = 
=
/ take into account that 4p > 2for 0.6 £ p £ 1 /
= 
=
5 * (1 – 0.36) =
5 * 0.64 = 3.2
Compute the value of f(2, 1) in terms of f(1, 2):
f(2, 1) = = 
=
/ take into account that 3.2p
> 1 for 0.6 £ p £ 1 /
= 
=
4 * (1 – 0.36) =
4 * 0.64 = 2.56
Algorithm realization
The function integral
computes the value of
the integral
I(a, k)
= 
for given real
numbers a and k. For t = 1, the probability of guessing p
is equal to one, the value of the integral I(a, k) is assumed to be
equal to max(a, k).
Below is the
area whose area is equal to the value of the integral 
:
Find the intersection point of the lines y = a and y = kp: a
= kp, wherefrom
p = a/k.
Let temp = a / k.
Let’s
consider the value of integral 
as a sum 
+ 
. Depending on the position of the point temp relative
to the points t and 1, compute the value of the integral I(a, k).
If t £ temp £ 1, then + =
a * (temp – t) + k * (1 – temp * temp) / 2
If temp £ t, then + = 
= k * (1 – t * t) / 2.
If temp > 1, then + = 
= a * (1 – t).
double integral(double
a, double k)
{
double s = 0,
temp = a / k;
if (t == 1) return max(a,k);
if (temp >
1) return a * (1 - t);
if (temp
>= t) s = a * (temp - t);
else temp =
t;
s += k * (1 – temp * temp) / 2;
return s / (1
- t);
}
The function f recursively computes f(n, a)
= 
.
double f(int
n, int a)
{
if (!n) return a;
double k =
f(n-1,2*a);
return
integral(a,k);
}
The main part of the program. Read the input
data and print the value of f(n,
1).
while(scanf("%d
%lf",&n,&t),n + t)
printf("%.3lf\n",f(n,1));