QOJ.ac

QOJ

Time Limit: 6 s Memory Limit: 1024 MB Total points: 17
Statistics

Problem

You've been playing roulette for a while in a local casino. Roulette is a simple casino game in which multiple players place bets on one or more numbers between 0 and 36 (inclusive). Next, a wheel is spun in one direction with a ball spinning in the other direction. The roulette wheel contains the same numbers 0 to 36. Some real roulette wheels also have a space labeled 00, but ours does not. Eventually, the ball falls on one of the numbers. If a player placed a bet on that particular number, he receives 36 times his bet (so the profit of that bet is 35 times the bet). All bets placed on other numbers lose.

Unfortunately, luck hasn't been on your side, and you have been losing all night long. At one point, you started to wonder whether the roulette game was fair or not, and after observing the game some more, you noticed a pattern that must be profitable for the casino: the ball always lands on one of the numbers that has the least total money bet on it! If multiple numbers tie for the least total money bet, the ball lands on one of those uniformly at random.

Of course, you'll be notifying the authorities about this foul play, but first you want to win your money back by exploiting your new-found knowledge. To do so, you wait until all other players have placed their bets and then place bets of your own. Unfortunately, you have a limited budget left, so you cannot bet more than that. You are allowed to bet on zero or more different numbers, and each of those bets can be any positive integer amount (perhaps with different amounts for different numbers), so as long as the sum of your bets does not exceed your budget. What is the maximum expected profit you can make?

Input

The first line of input gives the number of cases, T. T test cases follow. Each test case consists of two lines. The first line contains two integers: the budget you still have, B, and the number of numbers other players have placed bets on, N. The second line contains N integers Xi, the total amounts of money bet by other players on each of those different numbers.

Output

For each test case, output one line containing "Case #x: " followed by the maximum expected profit that you make if you place your bets optimally. A profit will be considered correct if it is within an absolute or relative error of 10-6 of the correct answer. See the FAQ for an explanation of what that means, and what formats of floating-point numbers we accept.

Limits

Time limit: 30 6 seconds per test set.

Memory limit: 1GB.

1 ≤ T ≤ 100.

1 ≤ N ≤ 37.

Small dataset (Test set 1 - Visible; 7 Points)

1 ≤ B, Xi ≤ 1,000.

Large dataset (Test set 2 - Hidden; 10 Points)

1 ≤ B, Xi ≤ 1012.

Sample

3
100 1
10
34 3
5 6 7
34 4
1 1 10 10
Case #1: 0
Case #2: 2
Case #3: 0.9428571429

In example 2, bet 1 on each of the 34 empty numbers for a guaranteed payback of 36, and a profit of 36 - 34 = 2. In example 3, bet 1 on each of the 33 empty numbers, so that you win 36 with probability 33/35. The gives an expected profit of 33/35 * 36 - 33.