Codeforces Round 253 (Div. 1) |
---|
Закончено |
Для проведения соревнования по программированию Андрею не хватает одной задачи. Но у него есть n друзей, которые всегда рады ему помочь. Он может попросить некоторых из них придумать задачу для соревнования. Про каждого своего друга Андрей знает одно число — вероятность того, что он придумает задачу, если его попросить.
Помогите Андрею выбрать людей, к которым следует обратится. Поскольку ему нужна только одна задача, то Андрей расстроится, если никто не придумает задачу или будет придумано больше одной задачи. Необходимо выбрать такой набор людей, что вероятность того, что Андрей не расстроится, будет максимальной.
В первой строке задано одно целое число n (1 ≤ n ≤ 100) — количество друзей Андрея. Во второй строке задано n вещественных чисел pi (0.0 ≤ pi ≤ 1.0) — вероятность того, что i-й друг сможет придумать задачу. Значения заданы не более чем с 6 знаками после десятичной точки.
Выведите одно вещественное число — вероятность того, что Андрей не расстроится при оптимальном выборе друзей. Ответ будет засчитан, если он отличается от правильного не более чем на 10 - 9.
4
0.1 0.2 0.3 0.8
0.800000000000
2
0.1 0.2
0.260000000000
В первом примере Андрею выгодно попросить только одного своего друга — наиболее надежного.
Во втором примере Андрею выгодно попросить придумать задачу всех своих друзей. Тогда вероятность того, что будет придумана ровно одна задача равна 0.1·0.8 + 0.9·0.2 = 0.26.
Название |
---|