托木斯克寒冷的冬夜非常无聊——没有人愿意在这个时候呆在街上。托木斯克的居民坐在温暖的公寓里消磨时光,发明了许多不同的游戏。其中一款游戏是“彩色叠叠乐”。
该游戏需要红、绿、蓝三种颜色的木块。用它们建造了一座 n 层的塔。每层由三个木块组成。每个级别中的块可以是任意颜色,但它们始终彼此靠近且平行。图中显示了此类塔的一个示例。
该游戏仅由一个人玩。每分钟,玩家都会掷出一个有六个面的特殊骰子。骰子的两面是绿色的,两面是蓝色的,一面是红色的,一面是黑色的。骰子显示每一面的概率相等。
如果骰子显示红色、绿色或蓝色,玩家必须在此时将任何该颜色的方块从塔中取出,这样塔才不会倒塌。如果不可能,玩家将等待直到一分钟结束,而不要触摸塔。如果骰子显示黑色一面,他还必须等到一分钟结束,不能碰触塔。不允许从塔的顶层(无论是否完工)拿走方块。
一旦玩家取出一个方块,他必须将其放在塔顶,以形成一个新的关卡或完成由先前放置的方块组成的上一层。新构建的关卡应具有与初始关卡相同的属性。如果上一关未完成,则禁止开始新一关。
为了让塔不倒塌,除了顶部之外的每一层都应该至少有一个方块。此外,如果在其中某些级别上正好剩下一个方块,并且该方块不是中间的方块,则塔会倒塌。
当塔内没有可以取出的方块以防止塔倒塌时,游戏结束。
这是托木斯克市居民发明的一款精彩游戏。我想知道如果玩家表现最佳的话,游戏可以持续多少分钟?如果玩家表现最佳,那么他会在任何时刻尝试选择他取出的方块,以最小化游戏持续时间的预期数量。
您的任务是编写一个程序来确定所需分钟数的预期数量。
输入
输入的第一行包含唯一的整数 n (2 ≤ n ≤ 6) — 塔的层数。
接下来是n行,从下到上描述塔的层次(第一行是塔的顶部)。每个级别由三个字符描述,其中第一和第三个字符设置该级别的边界块,第二个是中间块。描述块的字符具有以下值“R”(红色块)、“G”(绿色块)和“B”(蓝色块)之一。
输出
在输出的唯一一行中打印所寻求的数学期望值。如果答案的相对误差或绝对误差不超过 10 - 6,则认为答案是正确的。
示例
输入 #1
6 RGB GRG BBB GGR BRG BRB
输出 #1
17.119213696601992