P13269 [GCJ 2014 Finals] ARAM

League of Legends is a trademark of Riot Games. Riot Games does not endorse and has no involvement with Google Code Jam.

In the game League of Legends ${ }^{\mathrm{TM}}$, you can play a type of game called "ARAM", which is short for "All Random, All Mid". This problem uses a similar idea, but doesn't require you to have played League of Legends to understand it. Every time you start playing an ARAM game, you're assigned one of $\mathrm{N}$ "champions", uniformly at random. You're more likely to win with some champions than with others, so if you get unlucky then you might wish you'd been given a different champion. Luckily for you, the game includes a "Reroll" function. Rerolling randomly reassigns you a champion in a way that will be described below; but you can't reroll whenever you want to. The ability to reroll works like a kind of money. Before you play your first ARAM game, you begin with $\mathrm{R}$ RD ("reroll dollars"). You can only reroll if you have at least 1 RD, and you must spend 1 RD to reroll. After every game, you gain $1 / \mathrm{G}$ RD (where $\mathrm{G}$ is an integer), but you can never have more than $\mathrm{R}$ RD: if you have $\mathrm{R}$ RD and then play a game, you'll still have $\mathrm{R}$ RD after that game. If you have at least $1 \mathrm{RD}$, and you choose to reroll, you will spend $1 \mathrm{RD}$ and be re-assigned one of the $\mathrm{N}$ champions, uniformly at random. There's some chance you might get the same champion you had at first. If you don't like the champion you rerolled, and you still have at least $1 \mathrm{RD}$ left, you can reroll again. As long as you have at least $1 \mathrm{RD}$ left, you can keep rerolling. For example, if $\mathrm{R}=2$ and $\mathrm{G}=2$, and you use a reroll in your first game, then after your first game you will have $1.5 \mathrm{RD}$. If you play another game, this time without using a reroll, you will have $2.0 \mathrm{RD}$. If you play another game without using a reroll, you will still have $2.0 \mathrm{RD}$ (because you can never have more than $\mathrm{R}=2$ ). If you use two rerolls in your next game, then after that game you will have $0.5$ $\mathrm{RD}$. You will be given the list of champions, and how likely you are to win a game if you play each of them. If you play $10^{100}$ games and choose your strategy optimally, what fraction of the games do you expect to win?

The first line of the input gives the number of test cases, $\mathrm{T}$. $\mathrm{T}$ test cases follow. Each starts with a line containing three space-separated integers: $\mathrm{N}, \mathrm{R}$ and $\mathrm{G}$. The next line contains $\mathrm{N}$ space-separated, real-valued numbers $\mathrm{P}_{\mathrm{i}}$, indicating the probability that you will win if you play champion $\mathrm{i}$.

For each test case, output one line containing "Case #x: y", where $\mathrm{x}$ is the test case number (starting from 1) and $\mathrm{y}$ is the proportion of games you will win if you play $10^{100}$ games. $\mathrm{y}$ will be considered correct if it is within an absolute or relative error of $10^{-10}$ of the correct answer.

**Limits** - $1 \leqslant \mathrm{T} \leqslant 100$. - $0.0 \leqslant \mathrm{P}_{\mathrm{i}} \leqslant 1.0$. - $\mathrm{P}_{\mathrm{i}}$ will be expressed as a single digit, followed by a decimal point, followed by 4 digits. **Small dataset(22 Pts)** - Time limit: ~~60~~ 3 seconds. - $1 \leqslant \mathrm{N} \leqslant 1000$. - $1 \leqslant \mathrm{R} \leqslant 2$. - $1 \leqslant \mathrm{G} \leqslant 3$. **Large dataset(42 Pts)** - Time limit: ~~120~~ 5 seconds. - $1 \leqslant \mathrm{N} \leqslant 1000$. - $1 \leqslant \mathrm{R} \leqslant 20$. - $1 \leqslant \mathrm{G} \leqslant 20$.