Friday, November 26, 2004

Loaded Dice

With a single honest die, your an equal chance of rolling a number equivalent to the number of sides of the die. That is, with a standard six-sided die, you have equal chances of getting a 1, 2, 3, 4, 5, or 6. We can represent this dice as an ordered list of numbers, each number representing the relative probability of each side appearing.

An honest six-sided die could therefore be represented as [1,1,1,1,1,1]; the first number represents the relative probability of a “one” turning up; the second number represents the relative probability of a “two” turning up; and so on and so forth.

The game becomes a little more interesting if you combine two or more honest dice. Some numbers have more combinations, and therefore appear more often. Throw two six-sided honest die together, and the best number to bet on is a seven which gives you get a 1-in-6 chance. This is because there are 6 combinations which lead to a seven -- (1,6) (2,5) (3,4) (4,3) (5,2) (6,1) -- out of a total of 36 combinations, or 16.7%.

When you throw three six-sided die together, the best numbers to bet on are either 10 or 11. This is because there are 27 combinations which sum up to each number. This gives you a 12.5% chance of landing 10, and another 12.5% chance of landing an 11.

However, for cheating gamblers, these odds aren’t nearly good enough. This is why they use loaded dice. Loaded dice look like regular dice, except that they are weighted inside so as to favor some numbers more than others. For example, we could have a die where the “three” side is four times as likely to come up as any of the other sides.

Following our notation above, this relative probabilities of the loaded die could be represented as [1,1,4,1,1,1].

If you throw two loaded dice -- [1,1,4,1,1,1] and [1,1,1,4,1,1] -- the best number to bet on would still be a seven but the odds will have changed significantly in your favor. You would now get 21-in-81 chances of landing a seven, or 25.93%.

Remember that not all dice have six sides. Some dice have four sides, some have eight, some have 12, some have 20, and some have even funnier shapes.

If you were given a number of varying shapes of dice, some honest, some loaded, but each one consecutively numbered from one to whatever number of sides each had, what would be the best combination (or combinations) to bet on, and what is its probability?


INPUT
The input file consists of several test cases. Each test case starts with n (4 <= n <= 20), the number of dice for that test case. This is followed by n lines containing the probability list for each die.

Probabilities are indicated as a series of numbers separated by a single space, with each number representing the relative probability of one side of the die. The relative probability number is an integer between 1 and 200, inclusive.

OUTPUT
For each case, print out a header indicating the number of the test. On the next line, print out the most probable sum given the set of loaded dice. In case of a tie, print out the list of sums in ascending order, separating numbers with a space. Lastly, print the absolute probability of such an occurrence, accurate to 3 decimal places, rounding off if necessary. Print any trailing zeroes.