Colored Jenga

题意翻译

有一个叫 jenga的游戏，中文名叫作叠叠乐，如下图。 （叠叠乐的木板有红、绿、蓝三种颜色，放置的时候是一层横一层竖下来的。） 这个游戏只有 $1$ 个人玩！这个人有一个 $6$ 面骰子，掷出每个面的概率相等，六个面分别是绿、绿、蓝、蓝、红、黑。 现在这个人掷骰子，如果朝上的那一面不为黑，那么其在该回合可选择一块相应颜色的木板抽出并放到顶上，否则其停一回合。 抽木板的规则： 1. 不能从当前的最顶层抽木板，无论其是否已经完成。 2. 抽完木板之后这个结构必须是平衡的，即每层 $1,2,3$ 三个位置，或者是 $2$ 位置有一块木板，或者是 $1$ 和 $3$ 位置都有木板。 3. 放置木板的时候，如果顶层三个位置未填满，那么必须先填满顶层才能开始下一层。 4. 如果在以上三条规则下该回合没有木板可抽，那么停一回合，否则必须抽一块相应颜色的木板。 如果三种颜色的木板都不能抽了，那么游戏结束。 现在给定一个叠叠乐的初始局面，求在操作者争取总用时最少的情况下，游戏结束时，掷骰子的期望次数。 ## 输入 第一行一个正整数 $n$ ，表示叠叠乐游戏的层数。 接下来 $n$ 行从底到上分别描述每层的三块木板，每行 $3$ 个字母，表示对应木板的颜色， $R$ 表示红色， $B$ 表示蓝色， $G$ 表示绿色。 ## 输出 一行一个实数，表示答案，只有与标准答案相差 $10^{-6}$时才会被判为正确。

题目描述

Cold winter evenings in Tomsk are very boring — nobody wants be on the streets at such a time. Residents of Tomsk while away the time sitting in warm apartments, inventing a lot of different games. One of such games is 'Colored Jenga'. This game requires wooden blocks of three colors: red, green and blue. A tower of $ n $ levels is made from them. Each level consists of three wooden blocks. The blocks in each level can be of arbitrary colors, but they are always located close and parallel to each other. An example of such a tower is shown in the figure. The game is played by exactly one person. Every minute a player throws a special dice which has six sides. Two sides of the dice are green, two are blue, one is red and one is black. The dice shows each side equiprobably. If the dice shows red, green or blue, the player must take any block of this color out of the tower at this minute so that the tower doesn't fall. If this is not possible, the player waits until the end of the minute, without touching the tower. He also has to wait until the end of the minute without touching the tower if the dice shows the black side. It is not allowed to take blocks from the top level of the tower (whether it is completed or not). Once a player got a block out, he must put it on the top of the tower so as to form a new level or finish the upper level consisting of previously placed blocks. The newly constructed levels should have all the same properties as the initial levels. If the upper level is not completed, starting the new level is prohibited. For the tower not to fall, in each of the levels except for the top, there should be at least one block. Moreover, if at some of these levels there is exactly one block left and this block is not the middle block, the tower falls. The game ends at the moment when there is no block in the tower that you can take out so that the tower doesn't fall. Here is a wonderful game invented by the residents of the city of Tomsk. I wonder for how many minutes can the game last if the player acts optimally well? If a player acts optimally well, then at any moment he tries to choose the block he takes out so as to minimize the expected number of the game duration. Your task is to write a program that determines the expected number of the desired amount of minutes.

输入输出格式

输入格式

The first line of the input contains the only integer $ n $ ( $ 2<=n<=6 $ ) — the number of levels in the tower. Then $ n $ lines follow, describing the levels of the tower from the bottom to the top (the first line is the top of the tower). Each level is described by three characters, the first and the third of them set the border blocks of the level and the second one is the middle block. The character that describes the block has one of the following values 'R' (a red block), 'G' (a green block) and 'B' (a blue block).

输出格式

In the only line of the output print the sought mathematical expectation value. The answer will be considered correct if its relative or absolute error doesn't exceed $ 10^{-6} $ .

输入输出样例

输入样例 #1

6
RGB
GRG
BBB
GGR
BRG
BRB

输出样例 #1

17.119213696601992