The new term has just begun, so there are a lot of freshmen around. Not everyone has been lucky to be admitted to her/his desired university. As a result, many couples are now living in separate towns.
Of course, they try to see each other as often as they can. To facilitate this, the students have negotiated a deal with the coachmen. Instead of paying the regular price for a ride from one town to another, the price is determined by drawing a random integer between 1 and R inclusive, all numbers being equally likely. Unfortunately, this process repeats itself a few times whenever there is no direct connection between the towns a couple lives in. That makes the total cost of a journey quite unpredictable.
Help the couples determine the probability that one of them can afford a one-way trip to the other one. Given the number of towns and a list of direct connections, your program is supposed to process a list of couples. For each couple, you know their budget and where they live. Of course, they will always choose a route with the least expected price.
The first line contains the number of test cases t <= 10 that follow.
Each test case begins with a line that holds the number N of towns (1 <= N <= 100) followed by the
maximum price R of a single ticket (1 <= R <= 30). The following N lines contain N characters each.
The j-th character in the i-th line of these is “Y” if there is a direct connection between towns i and
j, but “N” otherwise. The j-th character in the i-th line is always the same as the the i-th character
in the j-th line. The j-th character in the j-th line is always “N”.
Each test case goes on with the number C of couples on a line by itself (1 <= C <= 1000). Then for
each couple there is a line that holds three integers a, b, and m. These numbers state that one of
them lives in town a, the other one in town b (1 <= a, b <= N, a != b), and the amount of money they
can spend is m (1 <= m <= 10000).
For each test case, print one line containing the word “Case”, a single space, and its serial number
(starting with 1 for the first test case). Then, output one line for each couple in this test case
containing the probability that they can afford a one-way journey according to the rules above. Your
answer need to round to 3rd decimal point. Print a blank line after each test
case.
2 3 4 NYY YNY YYN 1 1 3 1 4 7 NYNN YNYN NYNY NNYN 2 1 3 10 1 4 10
Case 1 0.250 Case 2 0.796 0.341
Migrated from old NTUJ.
SWERC 2008
| No. | Testdata Range | Score |
|---|