E. Сит тэмцээн

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

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

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

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

Сит Тэмцээний дүрмүүдийг хүн бүр мэддэг. Тэмцээнд $n$ Сит оролцоно. Тэмцээн нь эхний тулаанд тулалдах хоёр Сит-г санамсаргүй сонгохоос эхэлнэ. Хэн нэг нь хожигдож түүний оронд өмнө нь тулалдаагүй санамсаргүй сонгосон Сит гарч ирнэ. Сит тэмцээний тулаан бүр өрсөлдөгчдийн нэгнийх нь үхлээр дуусахыг хэлэх хэрэг байна уу? Тэмцээн зөвхөн нэг Сит үлдсэн үед л дуусна.

Жеди Иван санаандгүй байдлаар Сит Тэмцээний оролцогчдын жагсаалтад байсан. Гэсэн ч түүний Гэрэлт хүчний чадварууд маш хүчтэй ба тэр тэмцээнийг хэн эхлүүлэх эсвэл тулаан бүрийн дараа ялагдагчийн оронд хэн байх вэ гэсэн сонголтод нөлөөлж чадна: Мэдээж тэр энэ завшааныг ашиглах боломжийг алдахыг хүсэхгүй. Түүнд түүний ялалтын магадлалыг тооцоолоход туслана уу.

Оролт

Эхний мөрөнд нэг ширхэг бүхэл тоон утга $n$ ($1 ≤ n ≤ 18$) байх буюу Сит тэмцээний оролцогчдын тоо байна.

Дараагийн $n$ мөр бүрт $n$ бодит тоо байх ба эдгээр нь $p_{ij}$ ($0 ≤ p_{ij} ≤ 1$) матрицийг бүрдүүлнэ. Энэ матрицийн $p_{ij}$ элемент бүр нь $i$-р оролцогч $j$-р оролцогчийг тулаанд ялах магадлал байна.

Гол диагоналийн элементүүд буюу $p_{ii}$ нь тэгтэй тэнцүү байна. бүх ялгаатай $i$, $j$-н хувьд $p_{ij} + p_{ji} = 1$ тэгшитгэл биелэнэ. Бүх магадлалууд аравтын зургаа буюу түүнээс бага орны нарийвчлалтай өгөгдөнө.

Жеди Иван оролцогчдын жагсаалтын $1$ дугаар дээр байна.

Гаралт

Жеди Иван Тэмцээний дараа амьд үлдэх магадлалыг илэрхийлэх бодит тоог хэвлэ. Хариултын үнэмлэхүй болон харьцангуй алдаа нь $10^{ - 6}$-с ихгүй байх ёстой.

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

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

Оролт
3
0.0 0.5 0.8
0.5 0.0 0.4
0.2 0.6 0.0
Гаралт
0.680000000000000
Сэтгэгдлүүдийг ачааллаж байна...