1からMのランクを持つN × M 枚のカードのデッキがある.
それぞれのランクごとにN枚のカードが含まれている.
ランクmのカードのことを以下ではmと記述する.
デッキからL枚の手札をランダムに引くことができる.その手札
が与えられたパターンにマッチしているとボーナスが与えられる.パターンは,
以下のように記述される.
hand_pattern = card_pattern1 ' ' card_pattern2 ' ' ... ' ' card_patternL
card_pattern = '*' | var_plus
var_plus = variable | var_plus '+'
variable = 'a' | 'b' | 'c'
- hand_pattern
-
hand_pattern中の各card_patternがそれぞれ手札中の異なるカードにマッチすれば,
その手札はhand_patternにマッチする.
- card_pattern
-
card_patternがアステリスク('*')の時はどのカードにもマッチする.
文字'a', 'b', 'c'は変数を表し,同じ変数は同じランクのカードとマッチする.
変数の後に1個以上のプラス('+')を続けたパターンは,変数に対応するランクに'+'の個数を足して得られるラ
ンクのカードにマッチする.
変数の後に'+'をいくつか続けたパターンがhand_patternに含まれる時は,
同じ変数の後に'+'をより少ない数(ゼロを含む)続けたパターンがすべてhand_patternに含まれると
仮定してよい.たとえば,'a+++'がhand_patternに現れる時は,'a', 'a+', 'a++' が
hand_patternに現れる.
異なる変数の間には,表すランクについての制約はない.
たとえば,'a'に対応するランクと'b'に対応するランクは同じでもよいし,異なっていてもよい.
hand_patternの例を示す.パターン
a * b a b
は,'a'が3を, 'b'が10 を(または'a'が10を, 'b'が3を)表すとすると
3 3 10 10 9
とマッチする.
同じパターンは手札
3 3 3 3 9
ともマッチする.この時は,'a'も'b'も3を表す.パターン
a a+ a++ a+++ a++++
は手札
4 5 6 7 8
とマッチする.この場合,'a'は4になる.
デッキからランダムに取り出した手札が与えられたhand_patternにマッチする確率を求めるプログラムを作成しなさい.
入力は複数のデータセットからなる.それぞれのデータセットは以下の形式からなる.
N M L
card_pattern1 card_pattern2 ... card_patternL
最初の行は空白で区切られた三つの正の整数N, M, Lを含んでいる.Nは同ランクのカードの数, Mはランクの数,Lは手札の枚数を示す.N, M, Lは以下の制約を満たす.
1 ≤ N ≤ 7
1 ≤ M ≤ 60
1 ≤ L ≤ 7
L ≤ N × M
2行目はhand_patternを記述している.
入力の終わりは空白一つで区切られたゼロ3個からなる行によって示される.
1 1 1
a
3 3 4
a+ * a *
2 2 3
a a b
2 2 3
* * *
2 2 3
* b b
2 2 2
a a
2 3 3
a a+ a++
2 6 6
a a+ a++ b b+ b++
4 13 5
a a * * *
4 13 5
a a b b *
4 13 5
a a a * *
4 13 5
a a+ a++ a+++ a++++
4 13 5
* * * * *
4 13 5
a a a b b
4 13 5
a a a a *
7 60 7
a b a b c c *
7 60 7
* * * * * * *
7 60 7
a a+ a++ a+++ a++++ a+++++ a++++++
1 14 4
b a+ a a
0 0 0