105 - The 8th Zhejiang Provincial Collegiate Programming Contest - G
Palm up and palm down, also known as black and white, is a selection method used by a group to choose one person to do a task when no one has volunteered for it. Suppose there are n people at the beginning. For each round, everyone chooses to palm up (stand for white) or palm down (stand for black) simultaneously. If the numbers of both sides are nonzero and not equal, then the major ones will be free from the task, and the minor ones need to keep on playing this until only one person, the one who has to do the task, is left. If the numbers are just the same, then all of them keep on playing at the next round. The only exception is that when there are only two people, they use rock-paper-scissors instead to decide who the loser is. Otherwise, the game would never come to an end in these cases.
The rule of rock-paper-scissors is very simple: the players change their hands into one of three gestures -- rock, scissors and paper. Rock defeats scissors, scissors defeats paper, and paper defeats rock. The players keep on playing for one or more rounds until the winner is decided.
The game seems to be fair. But as different people have different habits, the outcome can be fun. In this problem, we assume that all people make decisions according to the given probability table, and your job is to tell the expected length the game is going to last and who is/are most probably to become the poor loser(s) and what is the corresponding probability.
There are multiple test cases. The first line of input is an integer T ≈ 100 indicating the number of test cases.
The first line of each test case is an integer 1 ≤ n ≤ 13 indicating the number of people. Then n lines, each line gives the information about one person: his/her name, the ratio of choosing to palm up and palm down and the ratio of choosing rock, paper and scissors. The name is an alphabetic string no longer than 20. All u, d, r, p, s are nonnegative integers no larger than 100, u + d > 0, r + p + s > 0.
For each test case, output the expectation of the rounds and the maximum probability to lose in the first line, with 3 decimal digits or "Infinity". Then, output the names of the people who will lose with that probability in lexicographical order. See sample for more details.
3 2 doraemon 50 50 100 0 0 dorami 50 50 100 0 0 2 doraemon 50 50 100 0 0 nobita 50 50 0 100 0 3 A 1 1 1 1 1 B 1 1 1 1 1 C 1 1 1 1 1
Infinity 0.000% doraemon dorami 1.000 100.000% doraemon 1.333 33.333% A B C
Author: Local Contests 2011 Committee
Contest: The 8th Zhejiang Provincial Collegiate Programming Contest