B. Осу тоглоцгооё!

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

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

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

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

Та Осу нэртэй тоглоом тоглож байв! Одоо бид уг тоглоомын хялбаршуулсан хувилбарыг танилцуулна. Уг тоглоомд нийт $n$ ширхэг удирдлага байна. Удирдлага бүрийн хувьд 2 үр дүн байх ба эдгээр нь зөв болон буруу гэсэн үр дүн байна. Зөв гэдгийг "$O$"-оор буруу гэдгийг "$X$"-ээр тэмдэглэх ба бүтэн тоглолт нь $n$ ширхэг "$O$" болон "$X$" тэмдэгтүүдийн дарааллаар бичигдэж болно.

Та уг дарааллыг ашиглан дараах байдлаар тоглолтын оноог тооцоолж болно: хамгийн урт дараалсан "$O$"-уудын блок болгоны хувьд та үүний уртын ("$O$" тэмдэгтүүдийн тоо) квадратыг тоглолтын оноон дээр нэмэх юм. Жишээлбэл, хэрэв таны тоглолт нь "$OOXOOOXXOO$" гэж бичигдсэн байвал нийт 3-н ширхэг хамгийн урт дараалсан "$O$"-уудын блок "$OO$", "$OOO$", "$OO$" байх ба таны оноо $2^{2} + 3^{2} + 2^{2} = 17$ болох юм. Хэрэв ямар ч зөв үр дүн байхгүй бол таны оноо $0$-тэй тэнцүү байх юм.

Та $i$-дахь $(1 ≤ i ≤ n)$ удирдлагыг зөв дарах магадлал нь $p_{i}$ болохыг мэдэж байв. Өөрөөр хэлбэл тоглолтын дарааллын $i$-дахь тэмдэгт нь $p_{i}$ магадлалтайгаар "$O$" байх ба $1 - p_{i}$ магадлалтайгаар "$X$" байна. Таны даалгавар бол уг тоглолтын хүлээгдэж буй оноог тооцоолох юм. Энд байгаа хүлээгдэж буй оноо нь магадлалын онолын хүлээгдэж буй утга буюу expected value болно.

Оролт

Эхний мөрөнд нийт удирдлагын тоо $n$ ($1 ≤ n ≤ 10^{5}$) өгөгдөнө. 2-дахь мөрөнд зайгаар тусгаарлагдсан $n$ ширхэг бодит тоонууд $p_{1}, p_{2}, ..., p_{n}$ $(0 ≤ p_{i} ≤ 1)$ өгөгдөнө.

Өгөгдсөн $p_{i}$-ууд нь таслалаас хойш хамгийн ихдээ 6-н орны нарийвчлалтай өгөгдөнө.

Гаралт

Таны тоглолтын хүлээгдэж буй оноог хэвлэнэ үү. Хэрэв таны хариултын абсолют болон харьцангуй алдаа нь $10^{ - 6}$-аас хэтрэхгүй бол зөвөөр тооцогдоно.

Орчуулсан: Баатархүү

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

Оролт
3
0.5 0.5 0.5
Гаралт
2.750000000000000
Оролт
4
0.7 0.2 0.1 0.9
Гаралт
2.489200000000000
Оролт
5
1 1 1 1 1
Гаралт
25.000000000000000

Тэмдэглэл

Эхний жишээг авч үзье. Нийт 8-н боломжит үр дүн байх юм. Тус бүрийнх нь магадлал 0.125 байна.

  • "$OOO$" $ -> $ $3^{2} = 9$;
  • "$OOX$" $ -> $ $2^{2} = 4$;
  • "$OXO$" $ -> $ $1^{2} + 1^{2} = 2$;
  • "$OXX$" $ -> $ $1^{2} = 1$;
  • "$XOO$" $ -> $ $2^{2} = 4$;
  • "$XOX$" $ -> $ $1^{2} = 1$;
  • "$XXO$" $ -> $ $1^{2} = 1$;
  • "$XXX$" $ -> $ $0$.

Иймд хүлээгдэж буй утга нь байна.

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