D. Вилбур ба Мод

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

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

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

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

Бяцхан гайхай Вилбур минж байхыг үнэхээр хүсдэг ба өнөөдөр тэр өөрийгөө минж гэж зориглож моднуудыг доош хазаж унагахаар шийдсэн.

Шулуун дээр ялгаатай байрлалд байрласан $n$ мод байна. $i$-р мод $x_{i}$ байрлалд байрласан. Моднуудын өгөгдсөн бүх байрлалууд ялгаатай.

Бүх моднууд ижил $h$ өндөртэй байна. Салхинаас хамаарч мод унах үедээ зүүн талруу $p$ магадлалтай эсвэл баруун талруу $1 - p$ магадлалтай унана. Хэрвээ мод унах явцдаа өөр модыг цохивол уг мод цохисон модтой ижил чиглэлд унана. Мод өөр модыг зөвхөн тэдгээрийн хоорондох зай $h$-с илэрхий бага үед л цохино.

Жишээлбэл $1$, $3$, $5$ ба $8$ байрлалд байрласан $4$ мод байна гэж төсөөлье, модны өндөр $h = 3$ ба $1$ байрлалд байгаа мод баруун тийшээ унасан. Энэ мод $3$ байрлалд байгаа модыг цохих ба энэ мод бас унаж эхэлнэ. Өөрийнхөө ээлжинд энэ мод $5$ байрлалд байгаа модыг цохих ба энэ мод бас унаж эхэлнэ. $8$ болон $5$-н хоорондох зай яг $3$ учир $8$ байрлалд байгаа мод унахгүй.

Хэрвээ босоо моднууд байх л юм бол Вилбур хамгийн зүүн талын босоо модыг $0.5$ магадлалтайгаар сонгоно эсвэл хамгийн баруун талын босоо модыг $0.5$ магадлалтайгаар сонгоно. Сонгогдсон мод доош унана. Хэрвээ ганц мод үлдэх юм бол Вилбур үргэлж үүнийг сонгоно. Газар унасан модуудаар хучигдмагц Вилбур бүх модыг унагасны дараах унасан модуудаар хучигдсан газрын нийт уртуудын дундаж утгыг мэдэхийг хүсч байна учир нь тэр унасан модон идэштэй найз үнээнүүддээ санаа нь зовж байна. Вилбурт туслана уу.

Оролт

Оролтын эхний мөрөнд хоёр бүхэл тоон утга $n$ $(1 ≤ n ≤ 2000)$ ба $h$ $(1 ≤ h ≤ 10^{8})$ мөн аравтын тооллын системийн зургаан оронгоос хэтрэхгүй бодит тоо $p$ ($0 ≤ p ≤ 1$) байна.

Оролтын хоёр дахь мөрөнд $n$ бүхэл тоон утга $x_{1}, x_{2}, ..., x_{n}$ $( - 10^{8} ≤ x_{i} ≤ 10^{8})$ тодорхой дараалалгүй байна.

Гаралт

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

Өөрөөр: таны хариулт $a$ ба шүүгчийн хариулт $b$ байсан гэж үзье. Шалгагч програм хэрвээ байвал таны хариултыг зөв гэж үзнэ.

Орчуулсан: Г.Мэндбаяр

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

Оролт
2 2 0.500000
1 2
Гаралт
3.250000000
Оролт
4 3 0.4
4 3 1 2
Гаралт
6.631200000

Тэмдэглэл

Эхний жишээний хувьд бидэнд 2 өндөртэй 2 мод байна.

Энд 3 боломж байна:

1. Хоёр мод зүүн тийшээ унах. магадлалтай баруун талын мод (зүүн модоо цохино) эхэлж унах эсвэл магадлалтай зүүн мод эхэлж унаад дараа нь баруун мод унана. Нийт магадлал нь байна.

2. Хоёр мод баруун тийшээ унах. Энэ нь (1)-тэй адил ба энэ явдлын тохиолдох магадлал нь .

3. Зүүн мод зүүн тийшээ ба баруун мод баруун тийшээ унах. Энэ нь үлдсэн боломж бөгөөд магадлал нь байх ёстой.

1 болон 2 тохиолдолд газрын хучигдсан хэсэг нь 3 нэгж бол 3 тохиолдолд газрын хучигдсан хэсэг нь 4 нэгж байна. Ингээд дундаж утга нь байна.

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