ARAM (Large)

League of Legends™ has a game mode called ARAM, short for All Random, All Mid. This problem uses a simplified version of its rules, so you do not need to have played the game.

Every time you start an ARAM game, one of $N$ champions is assigned to you uniformly at random. Your chance of winning depends on the champion, so an unlucky draw leaves you wishing for a different one. The game has a reroll function.

The right to reroll works like money. Before your first game you start with $R$ RD (reroll dollars). You can reroll only while you hold at least $1$ RD, and each reroll costs $1$ RD. After every game you gain $1/G$ RD, where $G$ is an integer, but your RD never goes above $R$. If you play a game while holding $R$ RD, you still hold $R$ RD when that game ends.

While you hold at least $1$ RD, choosing to reroll spends $1$ RD and assigns you one of the $N$ champions uniformly at random again. The champion you already had can come up again. If you dislike the champion you rerolled into and still hold at least $1$ RD, you can reroll again. You can keep rerolling as long as you hold at least $1$ RD.

For example, take $R = 2$ and $G = 2$ and suppose you use one reroll in your first game. After that game you hold $1.5$ RD. If you play the next game without rerolling, you hold $2.0$ RD after it. If you play another game without rerolling, you still hold $2.0$ RD, because you cannot go above $R = 2$. If you use two rerolls in the game after that, you hold $0.5$ RD once it ends.

You are given the list of champions and the probability that you win a game played with each of them. Compute the expected fraction of wins when you play $10^{100}$ games and choose your strategy optimally. The count $10^{100}$ is large enough that the answer agrees, to nine digits after the decimal point, with the largest long run average of the expected win probability per game.

The first line contains the number of test cases $T$. Then $T$ test cases follow. The first line of each test case contains three space separated integers $N$, $R$ and $G$. The next line contains $N$ space separated real numbers $P_1, P_2, \dots, P_N$, where $P_i$ is the probability that you win a game played with champion $i$.

For each test case, print one line in the form Case #x: y, where $x$ is the test case number starting from $1$ and $y$ is the expected fraction of games you win over $10^{100}$ games. Round $y$ and print exactly nine digits after the decimal point.

• $1 \le T \le 100$
• $1 \le N \le 1000$
• $1 \le R \le 20$
• $1 \le G \le 20$
• $0.0 \le P_i \le 1.0$
• $P_i$ is given as one digit, a decimal point, then four digits.

League of Legends is a trademark of Riot Games. Riot Games does not endorse this problem and has no involvement with it.