<ПРЕД Задача:
СЛЕД>
Задачу решил 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.
UserDateAttemptTimeCMSC
DAV16 mar 2010C++501.08176 
Jacob30 jun 2009C++901.33192 
Philip_PV18 feb 2009C++201.96195 
rvashegin11 jun 2008C++601.65197 
ripatti05 may 2011C++902.00200 
lutyj11 aug 2008C++101.41205 
Philip_PV18 feb 2009C++101.45206 
fetetriste31 may 2008C++101.11214 
RAVEman27 feb 2009C++201.15214 
Fat24 feb 2012C++1201.16215 
Chmeli_BSU04 aug 2008C++101.42215 
Языки
C++
37
C
2
Kylix
1
FPC
1
 > 
 > 
 > 
 > 
 > 
 > 
 > 
 > 
 > 
 > 

Такси 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 = 3.214.224.224