codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

930B.md (2386B)


      1 Source: https://codeforces.com/problemset/problem/930/B
      2 
      3 B. Game with String
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 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.
     22 
     23 Vasya 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.
     24 
     25 Note 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.
     26 
     27 Input
     28 
     29 The only string contains the string *s* of length *l* (3 ≤ *l* ≤ 5000), consisting of small English letters only.
     30 
     31 Output
     32 
     33 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.
     34 
     35 Formally, let your answer be *a*, and the jury's answer be *b*. Your answer is considered correct if ![](https://espresso.codeforces.com/58a50d50ad372e6c1d58fc9b6217d2b8de15e091.png)
     36 
     37 Examples
     38 
     39 Input
     40 
     41 ```
     42 technocup
     43 ```
     44 
     45 Output
     46 
     47 ```
     48 1.000000000000000
     49 ```
     50 
     51 Input
     52 
     53 ```
     54 tictictactac
     55 ```
     56 
     57 Output
     58 
     59 ```
     60 0.333333333333333
     61 ```
     62 
     63 Input
     64 
     65 ```
     66 bbaabaabbb
     67 ```
     68 
     69 Output
     70 
     71 ```
     72 0.100000000000000
     73 ```
     74 
     75 Note
     76 
     77 In the first example Vasya can always open the second letter after opening the first letter, and the cyclic shift is always determined uniquely.
     78 
     79 In 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.