Problem F
Playing with Coins
Input:
Standard
Input
Output: Standard Output
Jack and Jill like to play with coins. They are interested in the patterns generated after n times flip of a coin. As you know, in case of a fair coin if you flip the coin 3 times, you can get either of the following patterns.
|
HHH |
THH |
|
HHT |
THT |
|
HTH |
TTH |
|
HTT |
TTT |
The numbers of different patterns increase exponentially with the increase of number of flips. Jack and Jill categorizes all the patterns considering the sub-patterns they have –
|
H |
HHH, HHT, HTH, HTT, THH, THT, TTH, TTT |
|
HH |
HHH, HHT, THH |
|
HT |
HHT, HTH, HTT, THT |
|
TTH |
TTH |
It is not always possible to examine each pattern. So, some intelligent technique is necessary to do such task. The problem you need solve for Jack and Jill is to find the probability of getting patterns which will not contain any of the previously defined sub-patterns.
Each test case starts with a positive integer N (1<=N<=50) which means the number of flips and K (0<=K<=50) indicating the number of sub-patterns. Nest K lines will contain the sub-patterns which will be a sequence of H and T. All sub-patterns have same length and it will be at most 10. Input is terminated by N=K=0. This case should not be processed. There can be at most 100 test cases.
Output of each test case should consist of a line starting with “Case #: “where ‘#’ is the test case number. It should be followed by the probability of getting patterns which will not contain any of the given K sub-patterns. If the probability is non-zero, then print it in the form of “a/b” where a, b are properly reduced. If the probability is zero, then print “0” simply.
|
3 1 HH 3 1 HT 3 2 T H 0 0 |
Case
1: 5/8 Case
2: 1/2 Case 3: 0 |
Problem setter: Md. Kamruzzaman
Special Thanks: Jimmy Mårdell