{"problem":{"name":"D. Game with String","description":{"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 ","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF944D"},"statements":[{"statement_type":"Markdown","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.\n\n## Input\n\nThe only string contains the string _s_ of length _l_ (3 ≤ _l_ ≤ 5000), consisting of small English letters only.\n\n## Output\n\nPrint 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\n\n[samples]\n\n## Note\n\nIn 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.","is_translate":false,"language":"English"},{"statement_type":"Markdown","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_\"，他可以打开第四个字母并唯一确定移位。\n\n## Input\n\n输入仅包含一个长度为 #cf_span[l] #cf_span[(3 ≤ l ≤ 5000)] 的字符串 #cf_span[s]，仅由小写英文字母组成。\n\n## Output\n\n输出一个数 —— 本题的答案。你的答案若满足绝对误差或相对误差不超过 #cf_span[10 - 6]，则被视为正确。形式上，设你的答案为 #cf_span[a]，标准答案为 #cf_span[b]，当且仅当 \n\n[samples]\n\n## Note\n\n在第一个示例中，Vasya 总可以在打开第一个字母后打开第二个字母，此时循环移位总是能唯一确定。在第二个示例中，如果 #cf_span[t] 的第一个打开字母是 \"_t_\" 或 \"_c_\"，则 Vasya 仅通过再打开一个字母无法确定移位；而如果第一个字母是 \"_i_\" 或 \"_a_\"，他可以打开第四个字母并唯一确定移位。","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"Let $ s $ be a string of length $ l $, with characters indexed from $ 0 $ to $ l-1 $. Let $ 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\n$$\nt^{(k)}_i = s_{(i + k) \\mod l}, \\quad \\text{for } i = 0, 1, \\dots, l-1.\n$$\n\nVasya is told $ s $, and observes the first character of $ t^{(k)} $, i.e., $ t^{(k)}_0 = s_k $. Based on this, he chooses a position $ p \\in \\{1, 2, \\dots, l-1\\} $ to query the character $ t^{(k)}_p = s_{(p + k) \\mod l} $.\n\nLet $ A = \\{ k \\in \\{0, \\dots, l-1\\} \\mid s_k = c_0 \\} $, where $ c_0 $ is the first character observed. For each candidate $ k \\in A $, the pair $ (c_0, c_p) $ must uniquely determine $ k $, i.e., for any two distinct $ k_1, k_2 \\in A $, it must hold that:\n\n$$\ns_{(p + k_1) \\mod l} \\ne s_{(p + k_2) \\mod l}.\n$$\n\nVasya chooses $ p $ to maximize the probability that $ | \\{ k \\in A \\mid \\text{the pair } (s_k, s_{(p+k) \\mod l}) \\text{ uniquely identifies } k \\} | = |A| $, i.e., that all candidates consistent with the first character become distinguishable after querying position $ p $.\n\nLet $ P $ be the probability that Vasya wins when playing optimally.\n\nDefine, for each $ c \\in \\Sigma $ (alphabet), the set:\n\n$$\nA_c = \\{ k \\in \\{0, \\dots, l-1\\} \\mid s_k = c \\}.\n$$\n\nFor each $ c \\in \\Sigma $, and for each possible query position $ p \\in \\{1, \\dots, l-1\\} $, define the mapping:\n\n$$\nf_{c,p}(k) = s_{(p + k) \\mod l}, \\quad \\text{for } k \\in A_c.\n$$\n\nLet $ N_{c,p} $ be the number of distinct values in the multiset $ \\{ f_{c,p}(k) \\mid k \\in A_c \\} $. Then, the number of $ k \\in A_c $ that are uniquely identifiable under query $ p $ is exactly $ N_{c,p} $, since each distinct output corresponds to exactly one $ k \\in A_c $ (by injectivity of $ f_{c,p} $ on the preimage).\n\nThus, for fixed $ c $, the maximum number of identifiable shifts over all $ p $ is:\n\n$$\nM_c = \\max_{p \\in \\{1,\\dots,l-1\\}} N_{c,p}.\n$$\n\nThe probability of winning is then:\n\n$$\nP = \\frac{1}{l} \\sum_{c \\in \\Sigma} |A_c| \\cdot \\frac{M_c}{|A_c|} = \\frac{1}{l} \\sum_{c \\in \\Sigma} M_c.\n$$\n\nThat is, for each character $ c $, if it appears $ |A_c| $ times as the first character, then Vasya can uniquely identify $ M_c $ of the possible shifts $ k $ for which $ s_k = c $, by choosing the best $ p $. The total probability is the average over all $ l $ possible $ k $, weighted by the number of $ k $ that become uniquely identifiable.\n\n---\n\n**Final Formal Statement:**\n\nLet $ s \\in \\Sigma^l $, $ \\Sigma = \\{a, b, \\dots, z\\} $, $ l \\ge 3 $.\n\nFor each character $ c \\in \\Sigma $, define:\n- $ A_c = \\{ k \\in \\{0, 1, \\dots, l-1\\} \\mid s_k = c \\} $\n- For each $ p \\in \\{1, 2, \\dots, l-1\\} $, define $ f_{c,p}(k) = s_{(k + p) \\mod l} $ for $ k \\in A_c $\n- Let $ N_{c,p} = \\left| \\{ f_{c,p}(k) \\mid k \\in A_c \\} \\right| $ (number of distinct values)\n- Let $ M_c = \\max_{p \\in \\{1,\\dots,l-1\\}} N_{c,p} $\n\nThen the optimal win probability is:\n\n$$\n\\boxed{P = \\frac{1}{l} \\sum_{c \\in \\Sigma} M_c}\n$$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF944D","tags":[],"sample_group":[["technocup","1.000000000000000"],["tictictactac","0.333333333333333"],["bbaabaabbb","0.100000000000000"]],"created_at":"2026-03-03 11:00:39"}}