<ПРЕД Задача:
СЛЕД>
Задачу решил 41 пользователь: fetetriste, svirg, vi002, HeaDacHe, WsemirZ, zloy_mipt, rvashegin, JohnJones_001, FordPerfect, Cheryl, arti, Chmeli_BSU, lutyj, ignat, tourist, pmnox, tomek, mazahaka, UdH-WiNGeR, Philip_PV, defrager, RAVEman, knightry, wangyc, Jacob, daniel.ugra, DAV, Dest, mathematic, DD, Kuznetsov_S, ripatti, vitar, mkirsche, Fat, Bryak211, akk, checkil, NIGHTFIT, avg79, ilia.
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 

Такси 5

Time limit = 2 секунд(ы)

Memory limit = 4000

Таксист Даниил любит рассказывать своим пассажирам смешные шутки. Он считает своим долгом рассказать две смешные шутки за время в пути. Больше двух шуток он не рассказывает, чтобы не показаться навязчивым. Но если пассажир не смеётся над над его шуткой, то он решает, что эта шутка не смешная, и больше никогда ее не рассказывает. Если же шутка остается смешной, то Даниил может рассказывать ее другим пассажирам.

Даниил знает N смешных шуток. Для каждой шутки он знает степень её "прикольности" — вероятность того, что случайно выбранный пассажир будет над ней смеяться.

Новых шуток Даниил придумывать не умеет, а когда у него остается меньше двух смешных шуток, он разочаровывается в своей работе и увольняется. Но он не очень хочет увольняться, поэтому рассказывает шутки в таком порядке, чтобы ожидаемое число поездок было максимальным.

Требуется узнать ожидаемое число поездок, которые осталось совершить Даниилу.

Вход В первой строке записано целое число N, 0 ≤ N ≤ 10000. Во второй строке записаны N чисел pi — степени "прикольности" шуток, 0 ≤ pi ≤ 0.9999.

Выход Одно число — ожидаемое количество поездок. Относительная ошибка не должна превышать 10-9.

Вход#1
2
0.5 0.5
Выход#1
1.33333333333333

Вход#2
5
0.8 0.8 0.9 0.9 0.8
Выход#2
14.5876548893019

Автор:
Александр Поташев, спасибо Евгению Барскому за алгоритмическую идею.
24 мая 2008

<ПРЕД | Вернуться к списку задач | Искать сообщения в форуме | СЛЕД>


© acm.mipt DevGroup
The page was generated in 200ms

SW soft NIX
ID = 18.207.106.142