您和朋友一起玩游戏。下面列出了该游戏的说明。
你的朋友创建了 n 个长度相同的不同字符串 m 并告诉你所有的字符串。然后他随机选择其中一个。他等概率地选择字符串,即选择 n 个字符串中每一个的概率等于 $${\frac {1}{n}}$$。您想猜测您的朋友选择了哪根绳子。
为了猜测你的朋友选择了什么字符串,你可以向他提问。每个问题都有以下形式:“您选择的字符串中的 pos 位置上有什么字符?”当给定问题的答案唯一标识该字符串时,该字符串被视为已猜测。猜出字符串后,您就不再提问。
您没有特定的策略,因此您提出的每个问题都可能涉及尚未提及的立场。您的任务是确定猜测您朋友选择的字符串所需的预期问题数。
输入
第一行包含一个整数 n (1 ≤ n ≤ 50) - 你的朋友想出的字符串数量。
接下来的 n 行包含您的朋友创建的字符串。保证所有字符串都是不同的,并且只由大小英文字母组成。此外,所有字符串的长度都相同,并且在1到20之间(包含1和20)。
输出
打印单个数字 — 预期值。如果您的答案的绝对或相对误差不超过 10 - 9,则视为正确。
示例
输入 #1
2 aab aac
输出 #1
2.000000000000000
输入 #2
3 aaA aBa Caa
输出 #2
1.666666666666667
输入 #3
3 aca vac wqq
输出 #3
1.000000000000000
注意
在第一个示例中,字符串仅第三个位置的字符不同。所以只有以下几种情况可能:
- 您猜出一个问题中的字符串。事件的概率为$${\frac {1}{3}}$$;
- 你猜出两个问题中的字符串。事件的概率为 $$\frac{2}{3}$$ · $$\frac{1}{2}$$ = $${\frac {1}{3}}$$ (在这种情况下,第一个问题应该询问第三个问题以外的位置);
- 您在三个问题中猜出该字符串。事件的概率为 $$\frac{2}{3}$$ · $$\frac{1}{2}$$ · $$\frac{1}{1}$$ = $${\frac {1}{3}}$$;
因此,期望值等于 $$\frac{1+2+3}{3}=2$$
在第二个示例中,我们最多需要两个问题,因为任何一对问题都唯一标识该字符串。因此,预期问题数为 $$\frac{1}{3}+2\cdot\frac{2}{3}=\frac{5}{3}$$。
在第三个示例中,无论我们在第一个问题中询问什么位置,我们都会立即识别该字符串。