Задача Покрытие

Описание

Существует популярная игра – угадай цену машины. Предположим, стоимость новенькой машины измеряется пятизначным числом. Также предположим, что в текущей игре игроку дается два числа на выбор первой цифры, три числа на выбор второй цифры и т.д.

Участник выбирает по одному числу, для каждого разряда. И по условию, если хотя бы одно число было угадано правильно, игроку разрешается еще раз сделать выбор на все неправильные цифры. Игра продолжается до тех пор, пока игрок не угадает все числа ( игрок в этом случае выигрывает), либо на текущем ходу все числа которые он загадал, были неправильными (игрок проигрывает). Например, вы имеете выбор из пяти чисел для угадывания последней цифры стоимости машины – 1,3,5,8,9. Многие цены на машину заканчиваются числами 5 или 9. Предположим, можно утверждать что вероятность совпадения этих чисел равно 70 %, 35% что попадет число 5 и 35 % что попадет число 9. Остальные три числа имеют вероятность попадания 30/3 = 10 %. Если вы выбрали число 5 и оно оказалось ошибочным, но есть возможность продолжения игры, то из оставшихся четырех чисел вероятность попадания числа 9 – 54%, а остальных чисел приблизительно по 15 %.

Назовем числа 5 и 9 в этом примере известными кандидатами на угадывание. Например, для первой цифры если имеются числа 1 и 9 , то вероятность попадания 1 почти 100%, так как стоимость машины не может стоить 90 000 долларов. Ваша задача заключается в определении вероятности выигрыша при выборе оптимальной стратегии.

Формат входных данных

В первой строке входного файла дано число n – количество цифр (n <= 5) каждая из следующих n строк содержит числа mi, li, pi , где mi – количество выборов для угадывания цифры (разряда), находящейся на i-ой позиции числа (стоимости машины), li – количество известных кандидатов, p – вероятность, что один из известных кандидатов будет правильным. Если l=0 (нет кандидатов), то p=0. (0<=l<m<=10) , (0<=p<=1)

Формат выходных данных

в выходной файл выведите вероятность выигрыша при выборе оптимальной стратегии с точностью до трех знаков после запятой (окгрулить до трех знаков после запятой)