E. Галактик хоорондын аялал

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

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

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

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

Эрдэмтэд саяхан галактикууд болон оддын системүүдийн хооронд маш хол зайд аялах боломж олгодог сансрын обьектууд болох өтний нүхүүдийг нээсэн.

Эрдэмтэд хүрэх боломжтой $n$ галактикууд байгаа гэдгийг мэднэ. Та $1$ дугаартай галактик дээр байгаа ба $n$ дугаартай галактик дээр очих хэрэгтэй. $i$ галактикаас $j$ галактикт хүрэхийн тулд та $(i, j)$ өтний нүхэн дээр нисэх ёстой ба яг галактикийн нэг өдрийн дотор та өөрийгөө $j$ галактикаас олох болно.

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

Таны ажил бол хэрвээ та хамгийн тохиромжтой замаар явсан бол $1$-с $n$ дугаартай галактик ороход шаардлагатай цагийн хүлээгдэж байгаа утгыг олох юм.

Оролт

Оролтын эхний мөрөнд нэг ширхэг бүхэл тоон утга $n$ ($1 ≤ n ≤ 1000$) байх ба очиж болох галактикуудын тоо.

Тэгээд $n$ мөр $n$ баганатай матриц байна. $p_{ij}$ элемент бүр $i$-с $j$ хүргэх өтний нүх оршин байх магадлалыг илтгэнэ. Бүх магадлалууд хувиар өгөгдөх буюу бүхэл тоон утгууд байна. Үндсэн диогналийн бүх элементүүд $100$ байна.

Гаралт

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

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

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

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

Оролт
3
100 50 50
0 100 80
0 0 100
Гаралт
1.750000000000000
Оролт
2
100 30
40 100
Гаралт
3.333333333333333

Тэмдэглэл

Хоёр дахь жишээн дээр $1$-с $2$ дугаартай галактикт хүргэх өтний нүх өдөр бүр $0.3$ магадлалтайгаар оршин байна. Энэ үйл явдал тохиохоос өмнө хүлээх шаардлагатай өдрийн тооцоолох гэж буй утга нь байна.

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