prithivMLmods/Coder-Stat

1 2<h1>Generic Poker</h1>3<!-- end en only -->4 5<!-- begin en only -->6<p>7You have a deck of <i>N</i> &times; <i>M</i> cards. Each card in the deck has a rank. The range of ranks is 1 through <i>M</i>, and the deck includes <i>N</i> cards of each rank.8</p>9<!-- end en only -->10 11<!-- begin en only -->12<p>13We denote a card with rank <i>m</i> by <i>m</i> here.14</p>15<!-- end en only -->16 17 18 19<!-- begin en only -->20<p>21You can draw a hand of <i>L</i> cards at random from the deck.22If the hand matches the given pattern,23some bonus will be rewarded.24A pattern is described as follows.25</p>26<!-- end en only -->27<pre>28hand_pattern = card_pattern<sub>1</sub> ' ' card_pattern<sub>2</sub> ' ' ... ' ' card_pattern<sub><i>L</i></sub>29card_pattern = '*' | var_plus30var_plus = variable | var_plus '+'31variable = 'a' | 'b' | 'c'32</pre>33<p>34<dl>35<dt> hand_pattern36<dd> 37<!-- begin en only -->38A hand matches the hand_pattern if each card_pattern in the hand_pattern matches with a distinct card in the hand.39<!-- end en only -->40<dt> card_pattern41<dd> 42<!-- begin en only -->43If the card_pattern is an asterisk ('*'), it matches any card. 44Characters 'a', 'b', and 'c' denote variables and all the occurrences of the same variable match cards of the same rank.45A card_pattern with a variable followed by plus ('+')46characters matches a card whose rank is the sum of the rank corresponding to the variable47and the number of plus characters.48 49You can assume that, when a hand_pattern includes a card_pattern with50a variable followed by some number of plus characters, it also51includes card_patterns with that variable and all smaller numbers (including zero) of plus characters.52For example, if 'a+++' appears in a hand_pattern, card_patterns 'a',53'a+', and 'a++' also appear in the hand_pattern.54<!-- end en only -->55</dl>56</p>57 58<!-- begin en only -->59<p>60There is no restriction on which ranks different variables mean.61For example, 'a' and 'b' may or may not match cards of the same rank.62</p>63<!-- end en only -->64 65<!-- begin en only -->66<p>67We show some example hand_patterns. The pattern68<pre>69a * b a b 70</pre>71matches the hand:72<pre>733 3 10 10 974</pre>75with 'a's and 'b's meaning 3 and 10 (or 10 and 3),76respectively. This pattern also matches the following hand.77<pre>783 3 3 3 979</pre>80In this case, both 'a's and 'b's mean 3.  The pattern81<pre>82a a+ a++ a+++ a++++83</pre>84matches the following hand.85<pre>864 5 6 7 887</pre>88In this case, 'a' should mean 4. 89</p>90<!-- end en only -->91 92<!-- begin en only -->93<p>94Your mission is to write a program that computes the probability that95a hand randomly drawn from the deck matches the given hand_pattern.96</p>97<!-- end en only -->98 99 100 101<h3>Input</h3>102 103 104<!-- begin en only -->105<p>106The input is a sequence of datasets. Each dataset is formatted as follows.107</p>108<!-- end en only -->109 110<blockquote>111<i>N</i> <i>M</i> <i>L</i><br>112<i>card_pattern<sub>1</sub></i> <i>card_pattern<sub>2</sub></i> ... <i>card_pattern<sub>L</sub></i>113</blockquote>114 115<!-- begin en only -->116<p>117The first line consists of three positive integers <i>N</i>, <i>M</i>, and <i>L</i>.118<i>N</i> indicates the number of cards in each rank, <i>M</i> indicates the number of ranks, and <i>L</i> indicates the number of cards in a hand. <i>N</i>, <i>M</i>, and <i>L</i> are constrained as follows.119</p>120<!-- end en only -->121 122<blockquote>1231 &le; <i>N</i> &le; 7<br>1241 &le; <i>M</i> &le; 60<br>1251 &le; <i>L</i> &le; 7<br>126<i>L</i> &le; <i>N</i> &times; <i>M</i><br>127</blockquote>128 129<!-- begin en only -->130<p>131The second line describes a hand_pattern.132</p>133<!-- end en only -->134 135 136<!-- begin en only -->137<p>138The end of the input is indicated by a line containing three zeros 139separated by a single space.140</p>141<!-- end en only -->142 143 144 145 146 147<h3>Output</h3>148 149<!-- begin en only -->150<p>151For each dataset, output a line containing a decimal fraction which means the probability of a hand matching the hand_pattern.152</p>153<p>154The output should not contain an error greater than 10<sup>&minus;8</sup>.155</p>156<p>157No other characters should be contained in the output.158</p>159<!-- end en only -->160 161<h3>Sample Input</h3>162 163<pre>1641 1 1165a1663 3 4167a+ * a *1682 2 3169a a b1702 2 3171* * *1722 2 3173* b b1742 2 2175a a1762 3 3177a a+ a++1782 6 6179a a+ a++ b b+ b++1804 13 5181a a * * *1824 13 5183a a b b *1844 13 5185a a a * *1864 13 5187a a+ a++ a+++ a++++1884 13 5189* * * * *1904 13 5191a a a b b1924 13 5193a a a a *1947 60 7195a b a b c c *1967 60 7197* * * * * * *1987 60 7199a a+ a++ a+++ a++++ a+++++ a++++++2001 14 4201b a+ a a2020 0 0203</pre>204 205 206<h3>Output for the Sample Input</h3>207 208<pre>2091.00000000002100.88095238102111.00000000002121.00000000002131.00000000002140.33333333332150.40000000002160.12121212122170.49291716692180.04921968792190.02280912362200.00354603382211.00000000002220.00144057622230.00024009602240.00029677092251.00000000002260.00000010222270.0000000000228</pre>229