The Wheel of Fortune P59332


Statement
 

pdf   zip

html

“Welcome to the Wheel of Fortune! (aplause) Here, come here: do you see this big wheel? You can spin it as many times as you want, unless... well, you’ll see. There are n landing wedges. Some of them have a value from $1 to 10, which is the money you will get if you land on them. (Not much money, true. It’s the crisis). Great, right? And what about that 0, you ask? Well, every Wheel of Fortune has at least one of these. If you land on it, then, you lose everything. And you can’t spin the wheel no more.”

Are you ready for the problem? Given the n wedges in the Wheel of Fortune, please find the optimal strategy for deciding when to stop and when to keep spinning, and compute how much money you expect to obtain (on average) if you follow that optimal strategy.

For instance, for a wheel with n=3 and wedges 0, 0 and $9, the optimal strategy is to spin it once and, if you survive that spin, stop and cash the $9. The expected gain is $3.

Input

Input begins with the number of cases t, followed by t lines, each of them with n followed by the n values of the wedges, at least one of which will be a 0. Assume 1 ≤ n ≤ 104.

Output

Print t lines, each with the amount of dollars you can expect to make for the corresponding Wheel of Fortune, rounded to the closest cent, that is, with two digits after the decimal point. The input cases have no precision issues.

Public test cases

  • Input

    5
3 0 0 $9
2 $10 0
11 0 $1 $2 $3 $4 $5 $6 $7 $8 $9 $10
9 $10 $10 $10 $10 $10 $10 $10 $10 0
2 0 0

    Output

    $3.00
$5.00
$21.48
$31.18
$0.00
    • Information
    Author
    Omer Gimenez
    Language
    English
    Official solutions
    C++
    User solutions
    C++