```go
package main
import (
"bufio"
"bytes"
"fmt"
"math"
"os"
)
type Level = [3]uint8
var memo map[string]float64
const (
Empty = 0
Red = 1
Green = 2
Blue = 3
)
var p = [4]float64{
0,
1.0 / 6.0, // Red
2.0 / 6.0, // Green
2.0 / 6.0, // Blue
}
const pBlack = 1.0 / 6.0
func colorOf(b byte) uint8 {
switch b {
case 'R':
return Red
case 'G':
return Green
case 'B':
return Blue
default:
return Empty
}
}
func countLevel(l Level) int {
cnt := 0
if l[0] != 0 {
cnt++
}
if l[1] != 0 {
cnt++
}
if l[2] != 0 {
cnt++
}
return cnt
}
func canonicalize(levels []Level) []Level {
res := make([]Level, len(levels))
for i, l := range levels {
if l[0] > l[2] {
l[0], l[2] = l[2], l[0]
}
res[i] = l
}
return res
}
func encode(levels []Level) string {
var b bytes.Buffer
b.Grow(len(levels) * 4)
for _, l := range levels {
// canonical form assumes L<=R already
b.WriteByte('0' + l[0])
b.WriteByte('0' + l[1])
b.WriteByte('0' + l[2])
b.WriteByte('|')
}
return b.String()
}
func topIndex(levels []Level) int {
return len(levels) - 1
}
func hasAnyLegal(levels []Level) bool {
t := topIndex(levels)
for i := 0; i < t; i++ {
l := levels[i]
c := countLevel(l)
if c == 3 {
return true
}
if c == 2 {
if l[1] != 0 {
// exactly one of sides is present
if (l[0] != 0 && l[2] == 0) || (l[2] != 0 && l[0] == 0) {
return true
}
}
}
}
return false
}
func topAddPositions(levels []Level) []int {
t := topIndex(levels)
l := levels[t]
c := countLevel(l)
if c < 3 {
res := make([]int, 0, 3-c)
for j := 0; j < 3; j++ {
if l[j] == 0 {
res = append(res, j)
}
}
return res
}
return []int{0, 1, 2}
}
func legalRemovalsForColor(levels []Level, color uint8) [][2]int {
t := topIndex(levels)
moves := make([][2]int, 0)
for i := 0; i < t; i++ {
l := levels[i]
c := countLevel(l)
if c == 3 {
for j := 0; j < 3; j++ {
if l[j] == color {
moves = append(moves, [2]int{i, j})
}
}
} else if c == 2 {
if l[1] != 0 {
// exactly one side present
if l[0] != 0 && l[0] == color {
moves = append(moves, [2]int{i, 0})
}
if l[2] != 0 && l[2] == color {
moves = append(moves, [2]int{i, 2})
}
}
}
}
return moves
}
func expected(levels []Level) float64 {
levels = canonicalize(levels)
key := encode(levels)
if val, ok := memo[key]; ok {
return val
}
if !hasAnyLegal(levels) {
memo[key] = 0.0
return 0.0
}
minE := [4]float64{math.Inf(1), math.Inf(1), math.Inf(1), math.Inf(1)}
has := [4]bool{}
// For each color, compute minimal expected value among all legal actions (remove + place)
for ccol := uint8(1); ccol <= 3; ccol++ {
moves := legalRemovalsForColor(levels, ccol)
if len(moves) == 0 {
has[ccol] = false
continue
}
has[ccol] = true
best := math.Inf(1)
for _, mv := range moves {
i, j := mv[0], mv[1]
// Copy levels
newLevels := make([]Level, len(levels))
copy(newLevels, levels)
// Remove block
newLevels[i][j] = 0
// Place on top
addPos := topAddPositions(newLevels)
for _, ap := range addPos {
placed := make([]Level, len(newLevels))
copy(placed, newLevels)
t := topIndex(placed)
if countLevel(placed[t]) == 3 {
// start new level above
placed = append(placed, Level{0, 0, 0})
t = topIndex(placed)
}
placed[t][ap] = ccol
e := expected(placed)
if e < best {
best = e
}
}
}
minE[ccol] = best
}
denom := 1.0 - pBlack
numer := 1.0
for ccol := 1; ccol <= 3; ccol++ {
if has[ccol] {
numer += p[ccol] * minE[ccol]
} else {
denom -= p[ccol]
}
}
ans := numer / denom
memo[key] = ans
return ans
}
func main() {
in := bufio.NewReader(os.Stdin)
var n int
if _, err := fmt.Fscan(in, &n); err != nil {
return
}
lines := make([]string, n)
for i := 0; i < n; i++ {
fmt.Fscan(in, &lines[i])
}
// According to the statement, the first of the n lines is the top of the tower.
// Build levels from bottom to top: reverse the input order.
levels := make([]Level, 0, n)
for i := n - 1; i >= 0; i-- {
s := lines[i]
var l Level
l[0] = colorOf(s[0])
l[1] = colorOf(s[1])
l[2] = colorOf(s[2])
levels = append(levels, l)
}
memo = make(map[string]float64, 1<<16)
res := expected(levels)
fmt.Printf("%.10f\n", res)
}
```