{"raw_statement":[{"iden":"statement","content":"Vasya and Kolya play a game with a string, using the following rules. Initially, Kolya creates a string _s_, consisting of small English letters, and uniformly at random chooses an integer _k_ from a segment \\[0, _len_(_s_) - 1\\]. He tells Vasya this string _s_, and then shifts it _k_ letters to the left, i. e. creates a new string _t_ = _s__k_ + 1_s__k_ + 2... _s__n__s_1_s_2... _s__k_. Vasya does not know the integer _k_ nor the string _t_, but he wants to guess the integer _k_. To do this, he asks Kolya to tell him the first letter of the new string, and then, after he sees it, open one more letter on some position, which Vasya can choose.\n\nVasya understands, that he can't guarantee that he will win, but he wants to know the probability of winning, if he plays optimally. He wants you to compute this probability.\n\nNote that Vasya wants to know the value of _k_ uniquely, it means, that if there are at least two cyclic shifts of _s_ that fit the information Vasya knowns, Vasya loses. Of course, at any moment of the game Vasya wants to maximize the probability of his win."},{"iden":"input","content":"The only string contains the string _s_ of length _l_ (3 ≤ _l_ ≤ 5000), consisting of small English letters only."},{"iden":"output","content":"Print the only number — the answer for the problem. You answer is considered correct, if its absolute or relative error does not exceed 10 - 6.\n\nFormally, let your answer be _a_, and the jury's answer be _b_. Your answer is considered correct if"},{"iden":"examples","content":"Input\n\ntechnocup\n\nOutput\n\n1.000000000000000\n\nInput\n\ntictictactac\n\nOutput\n\n0.333333333333333\n\nInput\n\nbbaabaabbb\n\nOutput\n\n0.100000000000000"},{"iden":"note","content":"In the first example Vasya can always open the second letter after opening the first letter, and the cyclic shift is always determined uniquely.\n\nIn the second example if the first opened letter of _t_ is \"_t_\" or \"_c_\", then Vasya can't guess the shift by opening only one other letter. On the other hand, if the first letter is \"_i_\" or \"_a_\", then he can open the fourth letter and determine the shift uniquely."}],"translated_statement":[{"iden":"statement","content":"Vasya 和 Kolya 玩一个关于字符串的游戏，规则如下：最初，Kolya 创建一个由小写英文字母组成的字符串 #cf_span[s]，并从区间 #cf_span[[0, len(s) - 1]] 中均匀随机选择一个整数 #cf_span[k]。他将字符串 #cf_span[s] 告诉 Vasya，然后将其向左循环移动 #cf_span[k] 位，即生成一个新字符串 #cf_span[t = sk + 1sk + 2... sns1s2... sk]。Vasya 不知道整数 #cf_span[k]，也不知道字符串 #cf_span[t]，但他希望猜出 #cf_span[k]。为此，他要求 Kolya 告诉他新字符串的第一个字母，然后在看到该字母后，选择一个位置打开另一个字母。\n\nVasya 明白他无法保证获胜，但他希望知道在最优策略下获胜的概率。你需要计算这个概率。\n\n注意，Vasya 希望唯一确定 #cf_span[k] 的值，这意味着如果存在至少两个 #cf_span[s] 的循环移位与 Vasya 已知的信息一致，则 Vasya 失败。当然，在游戏的任何时刻，Vasya 都希望最大化自己获胜的概率。\n\n输入仅包含一个长度为 #cf_span[l] #cf_span[(3 ≤ l ≤ 5000)] 的字符串 #cf_span[s]，仅由小写英文字母组成。\n\n输出一个数字 —— 本题的答案。你的答案若满足绝对误差或相对误差不超过 #cf_span[10 - 6]，则被视为正确。\n\n形式上，设你的答案为 #cf_span[a]，评测标准答案为 #cf_span[b]，当且仅当 \n\n在第一个示例中，Vasya 总可以在打开第一个字母后打开第二个字母，此时循环移位总是能被唯一确定。\n\n在第二个示例中，若 #cf_span[t] 的第一个打开字母是 \"_t_\" 或 \"_c_\"，则 Vasya 仅通过再打开一个字母无法确定移位；而若第一个字母是 \"_i_\" 或 \"_a_\"，他可以打开第四个字母并唯一确定移位。"},{"iden":"input","content":"输入仅包含一个长度为 #cf_span[l] #cf_span[(3 ≤ l ≤ 5000)] 的字符串 #cf_span[s]，仅由小写英文字母组成。"},{"iden":"output","content":"输出一个数字 —— 本题的答案。你的答案若满足绝对误差或相对误差不超过 #cf_span[10 - 6]，则被视为正确。形式上，设你的答案为 #cf_span[a]，评测标准答案为 #cf_span[b]，当且仅当 "},{"iden":"examples","content":"输入\ntechnocup\n输出\n1.000000000000000\n输入\ntictictactac\n输出\n0.333333333333333\n输入\nbbaabaabbb\n输出\n0.100000000000000"},{"iden":"note","content":"在第一个示例中，Vasya 总可以在打开第一个字母后打开第二个字母，此时循环移位总是能被唯一确定。\n\n在第二个示例中，若 #cf_span[t] 的第一个打开字母是 \"_t_\" 或 \"_c_\"，则 Vasya 仅通过再打开一个字母无法确定移位；而若第一个字母是 \"_i_\" 或 \"_a_\"，他可以打开第四个字母并唯一确定移位。"}],"sample_group":[],"show_order":[],"formal_statement":"Let $ s $ be a string of length $ l \\geq 3 $, consisting of lowercase English letters.\n\nLet $ k \\in \\{0, 1, \\dots, l-1\\} $ be chosen uniformly at random. Define the cyclic shift $ t^{(k)} $ of $ s $ by $ k $ positions to the left as:\n$$\nt^{(k)}_i = s_{(i + k) \\bmod l}, \\quad \\text{for } i = 0, 1, \\dots, l-1.\n$$\n\nVasya is told $ s $, and observes $ t^{(k)}_0 $ (the first character of the shifted string). Then, he chooses an index $ j \\in \\{1, 2, \\dots, l-1\\} $ to observe $ t^{(k)}_j $. After seeing $ (t^{(k)}_0, t^{(k)}_j) $, he must uniquely determine $ k $.\n\nLet $ A $ be the set of all possible pairs $ (c_0, c_j) $ that can be observed, where $ c_0 = t^{(k)}_0 $, $ c_j = t^{(k)}_j $, for some $ k $. For each such pair, define the set of possible shifts:\n$$\nK(c_0, c_j) = \\left\\{ k \\in \\{0, \\dots, l-1\\} \\,\\middle|\\, s_k = c_0 \\text{ and } s_{(k+j) \\bmod l} = c_j \\right\\}.\n$$\n\nVasya wins if $ |K(c_0, c_j)| = 1 $. He chooses $ j $ (depending on $ c_0 $) to maximize the probability of winning.\n\nLet $ f(c_0) = \\max_{j \\in \\{1,\\dots,l-1\\}} \\Pr[ |K(c_0, c_j)| = 1 \\mid t^{(k)}_0 = c_0 ] $.\n\nThe overall winning probability is:\n$$\nP = \\frac{1}{l} \\sum_{k=0}^{l-1} f(s_k) = \\sum_{c \\in \\Sigma} \\left( \\frac{\\text{freq}(c)}{l} \\cdot f(c) \\right),\n$$\nwhere $ \\text{freq}(c) = |\\{ i \\mid s_i = c \\}| $, and $ f(c) = \\max_{j=1}^{l-1} \\frac{ |\\{ k \\mid s_k = c \\text{ and } s_{(k+j) \\bmod l} = d \\text{ for some unique } d \\text{ s.t. } |K(c,d)|=1 \\}| }{ \\text{freq}(c) } $.\n\nMore precisely, for each character $ c $, define:\n$$\nf(c) = \\max_{j=1}^{l-1} \\left( \\frac{1}{\\text{freq}(c)} \\cdot \\left| \\left\\{ k \\mid s_k = c \\text{ and } \\left| \\left\\{ k' \\mid s_{k'} = c \\text{ and } s_{(k'+j) \\bmod l} = s_{(k+j) \\bmod l} \\right\\} \\right| = 1 \\right\\} \\right| \\right)\n$$\n\nThen:\n$$\n\\boxed{P = \\sum_{c \\in \\Sigma} \\left( \\frac{\\text{freq}(c)}{l} \\cdot \\max_{j=1}^{l-1} \\left( \\frac{ \\left| \\left\\{ k : s_k = c \\text{ and } \\left| \\left\\{ k' : s_{k'} = c \\text{ and } s_{(k'+j) \\bmod l} = s_{(k+j) \\bmod l} \\right\\} \\right| = 1 \\right\\} \\right| }{ \\text{freq}(c) } \\right) \\right)}\n$$","simple_statement":null,"has_page_source":false}