Czech ACM Student Chapter
Czech Technical University in Prague
Charles University in Prague
Technical University of Ostrava
acm
ˇ a
Slovak University of Technology
Pavol Jozef Saf´rik University in Koˇice
s
cz
ˇ
University of Zilina
Masaryk University
Matej Bel University in Bansk´ Bystrica
a
University of West Bohemia
CTU Open Contest 2018
Numbers Generator
numbers.c, numbers.cpp, numbers.c11, Numbers.java, numbers.py
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 ≤ W ≤ 10, 1 ≤ B ≤ 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
Output for Sample Input 1
11
2.0
H
Sample Input 2
Output for Sample Input 2
23
5.0
HHT
THT
Output for Sample Input 3
Sample Input 3
7.0
23
HHH
HHT
