P13301 [GCJ 2013 #3] Observation Wheel

一个观光摩天轮由 $N$ 个乘客舱组成，这些舱按圆环排列，并且缓慢旋转。每当一个舱经过入口时，等待的人可以进入该舱。 在本题中，舱非常小，每个舱只能容纳一人。因此，如果当前经过入口的舱已被占用，等候的人只能继续等待下一个舱到来。如果下一个舱也已被占用，则继续等待下一个，以此类推，直到遇到一个空舱为止。为简化问题，我们不考虑乘客离开舱的情况——假设所有人上舱后都会一直随摩天轮旋转。 为了避免乘客因等待时间过长而失望，我们引入了灵活的定价方案：如果某人到达摩天轮时，经过入口的第一个舱是空的，她需支付 $N$ 美元；如果第一个舱被占用，需要等到第二个舱，则支付 $N-1$ 美元；如果前两个舱都被占用，需要等到第三个舱，则支付 $N-2$ 美元；一般来说，如果她需要等待 $K$ 个已占用舱，则支付 $N-K$ 美元。最坏的情况是，前 $N-1$ 个舱都被占用，只剩最后一个空舱，此时只需支付 $1$ 美元。 假设乘客到达摩天轮的时间是随机的，因此对每位乘客来说，第一个经过入口的舱是等概率独立选取的。并且假设在有乘客等候进入时，不会有新的乘客到来，因此我们无需考虑排队问题。每位乘客总是选择第一个空舱进入。 现在给出舱的总数及哪些舱已被占用。请问直到所有舱都被占满之前，我们平均能赚到多少钱？

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

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

**样例说明** 以第一个样例为例，共有九种可能性，每种概率为 $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 完成。