Tour Bets ---- ---- Tourists come to the colorful Kingdom of Fate to tour its quaint villages and spin the fantastic wheels of fortune in each village. There are rewards for those who do so, both emotional and monetary, but we need not go into those here. There are also rewards for the bookies of Fate who take on the following interesting kind of bet. Every tourist records the villages they visit and the result of their spinning the wheel of fortune in that village. The bookies publish the lists of spin results for each tourist and take bets on the list of villages visited by the tourist, which of course is not published until the day the bets are paid. Each wheel of fortune is divided into 50 parts each labeled with a capital letter. The tourists visit the villages by traveling roads between them, taking a whole day on each road, and resting one night in the village at the end of the road before traveling on to the next village the next day. They spin the wheel at a village as soon as they arrive at the village. Tours start and end at the kingdom's only port, which has no wheel. A friend of yours has made a model of Fate that gives the probability that a tourist who traveled a road one day will travel another road on the next day. It is also possible for the tourist to double back. The 50 possible outcomes of each wheel are equally probable and known. You have been asked to compute a list of the most probable tours for a tourist given the spin results of the tourist and your friend's model. Input ----- For each test case, first a line that gives the test case name. Then a line of the form V L B giving the number of villages V, length of output list L, and number of bets B. This is followed by V lines each containing 50 characters that list the wheel labels for village 1, 2, 3, ..., V in order. Next are lines of the form: w1 w2 w3 p(w1,w2,w3) Here w1, w2, and w3 are location IDs. These can be village IDs over the range 1, 2, 3, ..., V, or they can be the port ID 0. In the following v1, v2, v3 are village IDs, but NEVER the port ID. Then p(w1,w2,w3) is a probability defined as follows: p(w1,w2,v3) is the probability of going to village v3 if the last two places the tour was at are w1 and w2, respectively, and the tour does not go back to the port. Note that p(0,0,v3) is the probability the tour starts at v3. p(w1,v2,0) = 1 if and only if there is a road from v2 to the port and w1 != v2, = 0 otherwise, Also it is true that: p(w1,v2,v2) = 0 p(v1,v1,w2) = 0 p(v1,0,v3) = 0 p(v1,0,0) = 1 p(0,0,0) = 0 if ( p(0,0,v2) > 0 ) and w1 != v2, then p(w1,v2,0) = 1 Probabilities not explicitly specified are zero; none of the explicitly specified probabilities are zero. Lastly there are B lines each representing one bet. Each of these contains just a string of capital letters denoting the results of the tourist wheel spins. The number of letters in one line is the number of villages T visited by the tourist (excluding the port), and the i'th letter is the result of the tourist's wheel spin in the i'th village visited. 2 <= V <= 100 1 <= L <= 10 1 <= B <= 100 1 <= T <= 50 0 <= p(w1,w2,w3) <= 1.0 if w1 != w2 != 0 or w1 == w2 == 0: sum { p(w1,w2,v3) : 1 <= v3 <= V } = 1 Also see special cases above. Input ends with an end of file. Test case name lines are at most 80 characters. Output ------ For each test case, first an exact copy of the test case name line. Then for each of the B bets the following lines. First, a line copying the bet input. Then L lines of the form p v1 v2 ... vT where v1 v2 ... vT are the villages visited by the tour in order (T is the number of villages visited, i.e., the length of the bet line), and p is the probability of the tour according to the model. The L lines must be in order of descending p, and must be the L most probable tours given the bet. p is the conditional probability of the tour being v1, v2, ..., vT given that the spins are those of the bet. For example, in SAMPLE 1 below the joint probability of the bet ABB and the path 1 2 1 is 0.064, and the sum of the joint probability of the bet ABB over all paths (ALL PATHS, not just the 2 paths output) is 0.08, so the conditional probability of the path 1 2 1 given the bet ABB is 0.064 / 0.08 = 0.8. Similarly in SAMPLE 2 the joint probability of the bet ABC and the path 1 2 3 is 0.03024 and the sum of the joint probability of the bet ABC over all paths is 0.042775 so the conditional prob- ability of the path 1 2 3 given the bet ABC is 0.03024/0.042775 = 0.706955. The probabilities must be accurate to 5 digits of pre- cision and may be printed in scientific notation (use of double precision numbers with default %g format for C, C++, and JAVA suffices). The judge's input will be such that no two of the L+1 most probable tours have the same probability to within this accuracy. The probabilities may be very small and require exponential notation when printed. Sample Input ------ ----- -- SAMPLE 1 -- 2 2 4 AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABBBBBBBBBB BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBAAAAAAAAAA 0 0 1 0.5 0 0 2 0.5 1 0 0 1 2 0 0 1 0 1 0 1 0 2 0 1 1 2 0 1 2 1 0 1 0 1 2 1.0 0 2 1 1.0 1 2 1 1.0 2 1 2 1.0 AB BA ABB ABABABAB -- SAMPLE 2 -- 3 3 3 AAAAAAAAAAAAAAAAAAAAAAAAAAAAAABBBBBBBBBBBBBBBCCCCC BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBCCCCCCCCCCCCCCCAAAAA CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCAAAAAAAAAAAAAAABBBBB 0 0 1 0.5 0 0 2 0.25 0 0 3 0.25 1 0 0 1 2 0 0 1 3 0 0 1 0 1 0 1 0 2 0 1 0 3 0 1 1 2 0 1 1 3 0 1 2 1 0 1 2 3 0 1 3 1 0 1 3 2 0 1 0 1 2 0.4 0 1 3 0.6 0 2 1 0.2 0 2 3 0.8 0 3 1 1 1 2 1 0.3 1 2 3 0.7 1 3 1 1 2 1 2 0.6 2 1 3 0.4 2 3 1 0.2 2 3 2 0.8 3 1 2 0.9 3 1 3 0.1 3 2 1 1 AAA ABC ACB Sample Output ------ ------ -- SAMPLE 1 -- AB 0.941176 1 2 0.0588235 2 1 BA 0.941176 2 1 0.0588235 1 2 ABB 0.8 1 2 1 0.2 2 1 2 ABABABAB 0.999985 1 2 1 2 1 2 1 2 1.52586e-05 2 1 2 1 2 1 2 1 -- SAMPLE 2 -- AAA 0.7327 1 3 1 0.0915875 3 1 2 0.0569878 1 2 3 ABC 0.706955 1 2 3 0.142022 3 1 2 0.0504968 1 2 1 ACB 0.661697 1 3 1 0.117635 2 3 2 0.0827121 3 1 2 File: tourbets.txt Author: Bob Walton Date: Tue Oct 3 01:49:04 EDT 2017 The authors have placed this file in the public domain; they make no warranty and accept no liability for this file.