CTU Open Contest 2018 - Numbers Generator

View as PDF

Submit solution

Points: 20
Time limit: 0.6s
Memory limit: 256M

Problem types

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 Specification

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 Specification

Output a single number – the expected number of flips. The output will be considered correct if it differs by at most 0.1 from the correct answer.

Sample Input 1

1 1

Sample Output 1


Sample Input 2

2 3

Sample Output 2

Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported


There are no comments at the moment.