Description

一个观光摩天轮由 $N$ 个乘客舱组成，这些舱按圆环排列，并且缓慢旋转。每当一个舱经过入口时，等待的人可以进入该舱。

在本题中，舱非常小，每个舱只能容纳一人。因此，如果当前经过入口的舱已被占用，等候的人只能继续等待下一个舱到来。如果下一个舱也已被占用，则继续等待下一个，以此类推，直到遇到一个空舱为止。为简化问题，我们不考虑乘客离开舱的情况——假设所有人上舱后都会一直随摩天轮旋转。

为了避免乘客因等待时间过长而失望，我们引入了灵活的定价方案：如果某人到达摩天轮时，经过入口的第一个舱是空的，她需支付 $N$ 美元；如果第一个舱被占用，需要等到第二个舱，则支付 $N-1$ 美元；如果前两个舱都被占用，需要等到第三个舱，则支付 $N-2$ 美元；一般来说，如果她需要等待 $K$ 个已占用舱，则支付 $N-K$ 美元。最坏的情况是，前 $N-1$ 个舱都被占用，只剩最后一个空舱，此时只需支付 $1$ 美元。

假设乘客到达摩天轮的时间是随机的，因此对每位乘客来说，第一个经过入口的舱是等概率独立选取的。并且假设在有乘客等候进入时，不会有新的乘客到来，因此我们无需考虑排队问题。每位乘客总是选择第一个空舱进入。

现在给出舱的总数及哪些舱已被占用。请问直到所有舱都被占满之前，我们平均能赚到多少钱？

Input Format

第一行为测试用例数 $T$。接下来 $T$ 行，每行描述一个测试用例，仅由 .（表示空舱）和 X（表示已占用舱）组成。该行长度即为 $N$。第 $i$ 个字符为 X 表示第 $i$ 个舱已被占用，为 . 表示该舱为空。舱的编号即为它们经过入口的顺序，1 号舱后是 2 号舱，依次类推，最后一个舱后又回到第一个舱。

Output Format

对于每个测试用例，输出一行 "Case #x: y"，其中 $x$ 为测试用例编号（从 $1$ 开始），$y$ 为我们平均能赚到的钱（美元）。只要你的答案与正确答案的绝对或相对误差不超过 $10^{-9}$，就会被判为正确。关于浮点数输出格式和误差的说明请见常见问题。

5
.X.
X.X.
.XX.
X..XX.
.XX..X

Case #1: 4.66666666666667
Case #2: 6.00000000000000
Case #3: 5.75000000000000
Case #4: 13.4722222222222
Case #5: 13.5277777777778

Hint

样例说明

以第一个样例为例，共有九种可能性，每种概率为 $1/9$：

第一位乘客到达时，如果经过入口的下一个舱是：

• 第 1 个舱，且为空，则直接进入并支付 3 美元。之后，第二位乘客到来。如果下一个舱是：
  • 第 1 个舱（已占用），第 2 个舱也已占用，需等到第 3 个舱，支付 1 美元。总收入 4。
  • 第 2 个舱（已占用），需等到第 3 个舱，支付 2 美元。总收入 5。
  • 第 3 个舱（空），支付 3 美元。总收入 6。
• 第 2 个舱（已占用），需等到第 3 个舱，支付 2 美元。之后第二位乘客到来。如果下一个舱是：
  • 第 1 个舱（空），支付 3 美元。总收入 5。
  • 第 2 个舱（已占用，且第 3 个舱也已占用），需等到第 1 个舱，支付 1 美元。总收入 3。
  • 第 3 个舱（已占用），需等到第 1 个舱，支付 2 美元。总收入 4。
• 第 3 个舱（空），支付 3 美元。之后第二位乘客到来。如果下一个舱是：
  • 第 1 个舱（空），支付 3 美元。总收入 6。
  • 第 2 个舱（已占用，且第 3 个舱也已占用），需等到第 1 个舱，支付 1 美元。总收入 4。
  • 第 3 个舱（已占用），需等到第 1 个舱，支付 2 美元。总收入 5。

共九种情况，分别获得 3、4（三种）、5（三种）、6（两种）美元。平均收入为 $(1 \times 3 + 3 \times 4 + 3 \times 5 + 2 \times 6)/9 = 42/9 = 4.6666666666\dots$ 美元。

限制条件

• $1 \leq T \leq 50$

小数据集（8 分，测试集 1 - 可见）

• 时间限制：30 3 秒
• $1 \leq N \leq 20$

大数据集（23 分，测试集 2 - 隐藏）

• 时间限制：60 6 秒
• $1 \leq N \leq 200$

翻译由 ChatGPT-4.1 完成。