Problem G
Mahjong Madness
Mahjong is an ancient game similar to poker, where players build hands of tiles to win. You are playing a very simple version of the game, where there is only one player and one “suit” of tiles. Tiles can be numbered from $1-9$, and there are a total of $4$ of each numbered tile, resulting in a total of $36$ tiles.
You win the game once you complete a hand, which consists of $14$ tiles in total: $4$ “sets” of tiles and a “pair” of tiles. A “pair” of tiles is any pair of the same numbered tile, and a “set” of tiles can be either $3$ of the same numbered tile, or a $3$-length straight of numbered tiles ($1-2-3$ or $6-7-8$). If a tile is counted in a “set” or “pair”, it cannot be counted again in any other “set” or “pair”. No set can wrap around ($8-9-1$ is not a valid set).
In addition, different completed hands have different scores. At the start of each game, you will be given a number $x$ such that all tiles numbered $x$ will be worth more points. In this game, a completed hand is worth $1$ point, and each tile numbered $x$ in your completed hand is worth $1$ additional point. An incomplete hand is worth $0$ points.
In this version of the game, you are given a starting hand of $14$ tiles out of the total $36$ tiles, and you are given one turn where you must discard a tile from your hand and draw a new tile from the remaining unused tiles. Given a starting hand and the extra point tile, find the maximal expected point value after drawing and discarding a single tile.
Also note that you must discard a tile even if you are dealt
a winning starting hand.
In the first sample input, you would output $0.863636$, since if you discard the $1$, you complete your hand if you draw any tile other than $1$. This means that out of the $22$ tiles remaining, there are $19$ tiles that can complete the hand, and the resulting hand will be worth $1$ point, so the expected point value after discarding the $1$ would be $\frac{19}{22} = 0.863636$. An example of the hand that can be formed after discarding a $1$ and picking up a $9$ would be $3-3-3, \; \; 4-5-6, \; \; 7-8-9, \; \; 9-9-9, \; \; 8-8$. On the other hand, if you discard the $4$ or $7$ tile instead and wait for the $1$, your expected value is lower: $\frac{3}{22}*3 = 0.409091$.
Input
The first line of input contains a single integer $x$ that represents the extra point tile. ($1 \leq x \leq 9$)
The second line of input contains $14$ space-separated integers $n_ i$ representing the tiles in your starting hand. ($1 \leq n_ i \leq 9$)
Output
Output one line containing a single real value representing the maximal expected point value of your starting hand. Your answer will be considered correct if it is within an absolute or relative error of $10^{-6}$
| Sample Input 1 | Sample Output 1 |
|---|---|
1 1 3 3 3 4 5 6 7 8 8 8 9 9 9 |
0.863636 |
| Sample Input 2 | Sample Output 2 |
|---|---|
3 1 3 3 3 4 5 6 7 8 8 8 9 9 9 |
3.500000 |
| Sample Input 3 | Sample Output 3 |
|---|---|
1 1 1 2 2 4 4 6 6 7 7 8 8 9 9 |
0.000000 |
