D. Музей

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

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

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

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

Нэгэн өдөр Петя ба түүний найз Вася нар аялалд явж байхдаа нэгэн цайзан музейг үзэхээр болжээ. Музей нь $n$ өрөө болон $m$ коридортой бөгөөд аль ч өрөөнөөс бусад өрөөрүү очиж чаддаг.

Үүний дараа хоёр найз алхаж байгаад салж явахаар шийджээ. Тэд яг нэг өрөөнд 18 цагт уулзахаар болсон. Гэхдээ тэд нэг зүйл мартчихаж. Хэн нэгэн нь цагтаа ирэхгүй бол, нэг нь нөгөөдөхөө хайж гүйлдэж эхэлнэ. (Зарим нэгэн шалтгаанаас болоод бие биенийгээ дуудаж чадхааргүй болчихсон.)

Яарч сандраад байвал бүх үзүүлэнг үзэж чадахгүй. Тэгэхээр тэд энэхүү бодлогыг баримлахаар болов. Минут болгонд тэр хаашаа явахаа шийддэг - $p_{i}$ магадлалтайгаар тэр нэг минут хаашаа ч хөдлөдөггүй. Тэгвэл $1 - p_{i}$ магадлалтайгаар аль нэг хөрш өрөөрүүгээ коридороор дамжина. Аль ч хоёр өрөө нэгээс ихгүй коридоритой.

Хөвгүүд яг ижилхэн бодлогыг баримтлана. Коридориуд харанхуй болохоор тэд өөрсдийгөө олж харахгүй. Өөрөөр хэлбэл бие биентэйгээ уулзахгүйгээр нэг коридороор дамжиж болно гэсэн үг юм. Хөвгүүд бие биентэйгээ уулзах хүртлээ бодлогыг баримтлана. Энэ нь ямар нэг мөчид хоёулаа нэг өрөөнд байх явдал юм.

Бүх өрөөнүүдийн хувьд хоёулаа 18 цагт уулзах магадлалыг тооцож ол. Тэд $a$ болон $b$ өрөөнд байрлаж байгаа.

Оролт

Эхний мөрөнд дөрвөн бүхэл тоо өгөгдөнө:

  1. Өрөөний тоо болох $n$ $(1 ≤ n ≤ 22)$;
  2. Коридоруудын тоо болох $m$ ;
  3. Петяа болон Вася хоёрын байрлаж буй өрөөний тоо $a, b$ $(1 ≤ a, b ≤ n)$.

Дараагийн $m$ мөрөнд хос тоонууд өгөгдөнө - коридороор холбогдсон өрөөнүүдийн тоо. Дараагийн $n$ мөрөнд $p_{i}$ $(0.01 ≤ p_{i} ≤ 0.99)$ 4 оронгийн нарийвчлалтайгаар - $i$-дахь өрөөнд үлдэх магадлал.

Нэг өрөөнөөс бусад бүх өрөөрүү очих зам заавал олддог.

Гаралт

$n$ ширхэг бодит тоо. $i$-р тоо нь $i$-р өрөөнд яг 18 цагт уулзах магадлалыг 6 оронгийн нарийвчлалтайгаар хэвлэ.

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

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

Оролт
2 1 1 2
1 2
0.5
0.5
Гаралт
0.5000000000 0.5000000000 
Оролт
4 4 1 2
1 2
2 3
3 4
4 1
0.5
0.5
0.5
0.5
Гаралт
0.3333333333 0.3333333333 0.1666666667 0.1666666667 

Тэмдэглэл

Эхний жишээнд музей тэгш хэмтэй. Энэ нь эхний болон хоёрдугаар өрөөний магадлал нь ижилхэн бөгөөд нийлбэр нь нэгтэй тэнцүү. Тэгэхээр тус бүрийнх нь магадлал $0.5$.

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