C. Ялах стратеги

хугацааны хязгаарлалт 2 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Нэгэн их сургууль ACM ICPC v2.0 гэх нэртэй спорт прорамчлалын тэмцээнийг зохиожээ. Энэ тэмцээнд бидний мэдэх ACM ICPC-ээс нээх их ялгарахгүй. Жишээ нь финалын тэмцээнд оролцогч нар хоёроос их оролцохгүй г.м. Түүнчлэн нэг мэдэгдэхүйц ялгаа нь : тэмцээнд оролцож байгаа баг яг $n$ оролцогчтой байх ёстой.

ACM ICPC v2.0-д олон удаа оролцоод медаль авахгүй байгаа учрыг оюутнууд болон их сургуулийн захиргаа саяхан олж мэджээ. Үүний дараа их сургуулийн захиргаа оюутнуудынхаа бэлтгэлийг өөр аргаар боловсруулахаар болов. Маш их хугацааг бусад их сургуулиудын статистикийг авч үзэхэд : тухайн баг медаль авах магадлал нь хэдэн оюутан өмнөх финалд орж байсантай хамааралтай байв. Нөгөөгөөр бол бид $p_{0} ≤ p_{1} ≤ ... ≤ p_{n}$ байдаг $n + 1$ ширхэг бодит тоо мэдэж байгаа. Энд $p_{i}$ нь хэрэв оролцох гэж багт яг $i$ гишүүн нь өмнөх финалд оролцсон байхад медаль авах магадлал ба бусад $n - i$ гишүүд анх удаагаа орж байгаа.

Энэхүү хэрэгтэй мэдээллийг ашиглаад их сургуулийн захиргаа ямар тактик баримтлавал ACM ICPC v2.0 дундажаар хамгийн ихдээ хэдэн медаль авч болохыг мэдэхийг хүсч байна (бид маш олон жилийн дараах дундажийг олох гэж байгаа ба хязгааргүй олон оюутнууд байгаа гэж үзнэ). Та тэдэнд хамгийн ашигтай тактикийг санал болгож чадах уу? Бэлтгэлийг боловсруулах эхний шатанд их сургуулийн захиргаа медаль авах хамгийн их дундаж магадлалыг олохыг хүсч байна.

Их сургууль $k$-р дэлхийн финалд багаа илгээсэн гэж үзье. Энэхүү баг $a_{k}$ ширхэг өмнөх финалд оролцож байсан оюутнуудтай. ($0 ≤ a_{k} ≤ n$). Ямартай ч аль ч оролцогч хоёроос ихгүй оролцохгүй учраас дараах нөхцлийг хангах ёстой. .

Таны даалагавар бол байх дарааллын $Ψ$ хязгаар нь оршдог бөгөөд хамгийн их байх дарааллыг олох юм.

Энэхүү дараалал нь хязгааргүй олон гишүүнтэй учир $Ψ$ хязгаарын хамгийн их утгыг хэвлэхэд хангалттай.

Оролт

Эхний мөрөнд $n$ ($3 ≤ n ≤ 100$), $n$ бол багийн гишүүдийн тоо. Дараагийн мөр 6 оронгийн нарийвчлалтай $n + 1$ $p_{i}$ ($0 ≤ i ≤ n, 0 ≤ p_{i} ≤ 1$) бодит тоо - багт яг $i$ гишүүн өмнөх финалд оролцсон байхад медаль авах магадлал. $0 ≤ i ≤ n - 1$ бүрийн хувьд $p_{i} ≤ p_{i + 1}$ нөхцлийг хангана.

Гаралт

Хариу болох ганц бодит тоо - хамгийн сайн стратеги ашиглахад дундажаар авах медалийн магадлалыг 6 оронгийн нарийвчлалтай хэвлэнэ.

Орчуулсан: Б.Алтангэрэл

Жишээ тэстүүд

Оролт
3
0.115590 0.384031 0.443128 0.562356
Гаралт
0.4286122500
Оролт
3
1 1 1 1
Гаралт
0.9999999999

Тэмдэглэл

Хоёрдугаар тестэнд хэдэн оролцогчтой байх хамаагүй, байнга медаль авна.

Сэтгэгдлүүдийг ачааллаж байна...