← 返回题目列表

Codeforces · 930/B

B. 绳子游戏

中文机器翻译题面 查看原题

Vasya 和 Kolya 使用绳子玩游戏,规则如下。最初,Kolya 创建一个由小英文字母组成的字符串 s,并从 [0, len(s) - 1] 段中均匀随机选择一个整数 k。他告诉 Vasya 这个字符串 s,然后将其向左移动 k 个字母,即 i。 e.创建一个新字符串 t = sk + 1sk + 2... sns1s2... sk。 Vasya 不知道整数 k 也不知道字符串 t,但他想猜测整数 k。为此,他要求 Kolya 告诉他新字符串的第一个字母,然后在他看到它后,在某个位置再打开一个字母,Vasya 可以选择该字母。

Vasya 明白,他不能保证自己会赢,但他想知道如果他发挥最佳,获胜的概率。他希望你计算这个概率。

注意,Vasya想要唯一地知道k的值,这意味着如果s的至少两个循环移位符合Vasya已知的信息,则Vasya失败。当然,在比赛的任何时刻,瓦夏都希望最大化他获胜的可能性。

输入

唯一的字符串包含长度为 l (3 ≤ l ≤ 5000) 的字符串 s,且仅由小英文字母组成。

输出

打印唯一的数字 - 问题的答案。如果您的答案的绝对或相对误差不超过 10 - 6,则视为正确。

正式来说,让您的答案为 a,陪审团的答案为 b。如果 $${ \frac { | 则认为您的答案是正确的a - b | } { \operatorname* { m a x } ( 1, | b | ) } } \leq 1 0 ^ { - 6 }$$

示例

输入 #1

technocup

输出 #1

1.000000000000000

输入 #2

tictictactac

输出 #2

0.333333333333333

输入 #3

bbaabaabbb

输出 #3

0.100000000000000

注意

在第一个示例中,Vasya 始终可以在打开第一个字母后打开第二个字母,并且循环移位始终是唯一确定的。

在第二个示例中,如果 t 的第一个打开的字母是“t”或“c”,则 Vasya 无法通过仅打开另一个字母来猜测移位。另一方面,如果第一个字母是“i”或“a”,那么他可以打开第四个字母并唯一地确定移位。