At the local carnival you find a midway game advertising "TONS OF FABULOUS PRIZES". Certainly a fabulous prize or two would make your time worthwhile. It turns out that "TONS" is actually a bit of of an understatement. There are in fact infinitely many prizes available. Consequently, the game operator is willing to give you a chance to score multiple prizes in a single game (for a nominal fee).
After you hand over your money, the game operator gives you N coins. Each coin has the same probability p of landing on heads when flipped (and consequently probability 1 - p of landing on tails). She also gives you a goal, an integer K.
As long as you still have some coins remaining, you can select any number of them and flip them all simultaneously. These coins are then taken away. If at least K of them land on heads, you win a prize. If you play optimally, what is the expected number of prizes you'll manage to win?
Input
Input begins with an integer T, the number of times you play the game. For each attempt, there is a line containing the space-separated values N, K and p. N and K are integers, and p is given with at most 16 decimal places.
Output
For the ith attempt, print a line containing "Case #i: " followed by the expected number of prizes you'll win. Your output should have at most 10-6 absolute or relative error.
Constraints
1 ≤ T ≤ 100
1 ≤ N ≤ 3,000
1 ≤ K ≤ 3,000
0 ≤ p ≤ 1
Explanation of Sample
In the first case, flipping the coins together gives you a 75% chance of winning a prize. If you flip them separately, you get a 50% chance on each flip. The latter approach is better, giving you 1 expected prize rather than 0.75 expected prizes. In the second case, it is optimal to partition the ten coins into two sets of five. In the third case, it is optimal to flip all ten coins at once.
Sample input
Code: Select all
5
2 1 0.5
10 5 0.9
10 5 0.1
3000 50 0.123
3000 50 0.987Code: Select all
Case #1: 1.000000000
Case #2: 1.180980000
Case #3: 0.001634937
Case #4: 5.712907306
Case #5: 56.182751225