Cover Up
"Цена правильная" - популярное игровое шоу, в котором участники играют в различные игры, чтобы выиграть сказочные призы. Одна из игр на шоу назывется “Прятки”, в которой следует угадать 5-цифровое число (цену новой машины). Участникам предлагают два числа, из которых они должны выбрать первую цифру, три числа чтобы выбрать вторую цифру, и так далее. Участник выбирает по одному числу для каждой цифры (из множества еще не выбранных чисел для той цифры), после чего ему сообщают какие из них корректны; если хотя бы одна цифра правильная, участнику разрешают далее угадывать неверные цифры. Участники продолжают отгадывать, пока хотя бы одна из новых цифр является корректной. Игра заканчивается, либо когда все цифры отгаданы верно (игрок является победителем), либо после очередного хода ни одна из цифр не угадана правильно (проигрыш).
Typically this game is not sheer luck. For example, suppose you had the following five possibilities for the last digit: 1, 3, 5, 8 and 9. Many car prices end with either a 5 or a 9, so you might have, say, a 70% chance that one of these two numbers is correct; this breaks down to a 35% chance for either the 5 or the 9 and a 10% chance for each of the other three digits. Now say you pick the 5 and it’s wrong, but some other guess you made was right so you still get to play. With this additional information the probabilities for the remaining 4 numbers change: the probability for the 9 is now close to around 54%, while each of the other three numbers now has a little over a 15% chance. (We’ll let you figure out how we got these values). We’ll call the 5 and the 9 in the original group the known candidates, and typically there are known candidates in other columns as well. For example, if the two numbers for the first (high order) digit are 1 and 9, the contestant can be 100% sure that the 1 is the correct digit (there aren’t too many $90,000 cars to be given away).
For this problem, you are to determine the probability of winning the game if an optimal strategy for picking the numbers (based on probabilities such as those described above) is used.
Входные данные
Each test case will consist of two lines. The first will be n, the number of digits in the number to be guessed. The maximum value of n will be 5. The second line will contain n triplets of numbers of the form m l p where m is the number of choices for a digit, l is the number of known candidates, and p is the probability that one of the known candidates is correct. In all cases 0 ≤ l < m ≤ 10 and 0.0 ≤ p ≤ 1.0. Whenever l = 0 (i.e., when there are no known candidates) p will always be 0.0. A line containing a single 0 will terminate the input.
Выходные данные
Output for each test case is the probability of winning using optimal strategy. All probabilities should be rounded to the nearest thousandth, and trailing 0’s should not be output. (A 100% chance of winning should be output as 1.)