F. 变色彩灯

Erratic Lights

时间限制：2 秒 · 内存限制：1024 MiB

原题：NWERC 2025 E · 查看官方英文原文（英文 PDF 也已作为本题附件提供）

题目描述

一串彩灯共有 $n$ 个灯泡，每个灯泡当前为红、绿、蓝三种颜色之一。每次你可以选择并触碰一个灯泡；被触碰的灯泡会随机变为红、绿、蓝中的一种，每种颜色的概率均为 $1/3$，也可能保持原来的颜色。

你可以在每次操作后观察颜色，并据此决定下一次触碰哪个灯泡。你希望最终所有灯泡的颜色都相同，具体是哪一种颜色并不重要。

在采用最优策略的情况下，求需要触碰灯泡次数的最小期望值。如果最初颜色已经全部相同，可以立即停止，所需次数为 $0$。

输入格式

第一行包含一个整数 $n$（$1 \leq n \leq 100$）。

第二行是长度为 $n$ 的字符串，仅包含 $r$、$g$、$b$，分别表示各灯泡的初始颜色为红、绿、蓝。

输出格式

输出最小期望操作次数。答案的绝对误差或相对误差不得超过 $10^{-6}$。

样例

2
rb

3

3
ggg

0

5
rgbrg

7.5

原题版权归原作者及相应赛事评委会所有，采用 CC BY-SA 4.0 许可。中文译文为本练习赛整理，按相同许可发布。题号及中文标题作了调整，输入约束、样例和判题要求依照官方原题；图示及完整英文叙述请参阅英文原文附件。