405409: GYM101954 D Numbers Generator

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

D. Numbers Generatortime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

Among the most popular games in Binary casino is a game called "The Binary Generator". It is played by multiple players and with a single coin. Each player first chooses a sequence of heads and tails of a given length. After that, players or the casino start flipping the coin and the winner is the player whose sequence first appears as a contiguous subsequence of the flip results.

You believe all sequences chosen by players are equally good and so the choice of the sequence does not matter. However, after losing all of your money, you became somewhat doubtful of that. Write a program to prove you wrong. For a given list of sequences of heads and tails of the same length, write the expected number of coin flips which have to be performed until one of the players' chosen sequences appears as a contiguous subsequence in the flip sequence. The expected number of coin flips is the average length of a flip sequence over all possible flip sequences resulting in some player's victory, where each flip sequence is weighted by its probability.

Input

The first line of input contains two integers $$$W$$$ and $$$B$$$ ($$$1 \le W \le 10$$$, $$$1 \le B \le 30$$$), the number of players' sequences and the length of players' sequences, respectively. Next, $$$W$$$ lines follow, each consisting of a sequence of $$$B$$$ letters. Each letter is either "H" for heads or "T" for tails.

Output

Output a single number ­– the expected number of flips. The output will be considered correct if its relative error does not exceed $$$10^{-6}$$$.

ExamplesInput
1 1
H
Output
2.00000
Input
2 3
HHT
THT
Output
5.00000
Input
2 3
HHH
HHT
Output
7.00000

加入题单

上一题 下一题 算法标签: