A and B are playing a shooting game on a battlefield consisting of square-shaped unit blocks. The blocks are occupying some consecutive
columns, and the perimeter of the figure equals the perimeter of its minimal bounding box. The figure (a) below is a valid battlefield,
but (b) and (c) are not, because in (b), there is an empty column; in (c), the perimeter of figure is 14, but the perimeter of the
bounding box (drawn with dashed lines) is 12. With the help of gravity, each block is either located on another block,
or sitting on the ground. To make the battlefield look more exciting, it must not be a perfect rectangle (i.e. it is not allowed that
every column has the same height)
Here is the rule of the game:
- A and B shoot by turn. A starts first.
- Before shooting, the player first select one row with at least one block, and one of the two directions "left" and "right",
then shoot at this row along that direction. The power of the shoot is one of 1, 2 or 3, each with probability of 1/3. The power
of shoot is the number of blocks (not necessarily consecutive) that can be destroyed in this shoot. If the total number of blocks
on this row is less than the power of shoot, then all the blocks on this row is destroyed. For example, if the player chooses to
shoot the 3rd row from the bottom, with direction "right", power 2, and there are 4 blocks on this row, then the left-most two
blocks are destroyed.
- After each shoot, blocks in the air fall down vertically. The next player cannot shoot before all the blocks stop falling.
- He who destroys the last block wins.
Assume the starting battlefield is
. According to rule 1, A shoots first. The table below shows three (not all) possible outcomes
of the first shot:
Row(from bottom) | Direction | Power | Befrore Falling | Stable |
2 | Left | 1 |
| (Same as left) |
1 | Left | 2 |
|
|
1 | Right | 3 |
|
|
Assume Alice and Bob are both very clever (always follows the strategy that maximizes the probability he/she wins), what is the
probability that Alice wins?
There will be at most 25 test cases, each with two lines. The first line is a single integer n (
1n6), the number of
columns. The second line contains n integers h1, h2, ..., hn (
1hi6), the heights of the columns from
left to right. The battlefield is guaranteed to satisfy the restrictions in the problem (perimeter of figure equals that of
the minimal bounding box, and is not a perfect rectangle). Input is terminated by n = 0.
For each test case, print a single line, the probability that A wins, to six decimal points.
3
2 1 1
0
0.555556
Problemsetter: Rujia Liu, Special Thanks: Yiming Li, Tanaeem M Moosa & Sohel Hafiz