D. Подволк

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

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

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

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

Та Кодпорст 1-ээс $n$-ээр дугаарлагдсан $n$ инженерийн багт зарлуу мэргэжилтэнгээр ажиллах гэж байгаа. Та инженер бүрт дурсгалын зүйл өгөхийг хүссэн: Өөрийн улсын подволк (Кодпорст подволкууд маш үнэ цэнэтэй). Харамсалтай нь инженер бүрт багтах подволкны хэмжээг та мэдэхгүй. 1-ээс $m$ хүртэл дуугаарлагдсан $m$ өөр хэмжээнүүд байх ба инженер бүр нэг л хэмжээний подволконд багтна.

Та инженерүүдийн яс хэмжээг мэдэхгүй тул Жералд найзаасаа асуусан. Харамсалтай нь тээрээр яс хэмжээг бас л авч чадаагүй боловч тухайн хэмжээ $i$ инженерт таарах магадлал $j$ болохыг $i$ инженер бүрт цуглуулж чаджээ.

Та инженер бүрт нэг нэг подволк өгөхөөр төлөвлөсөн учраас яг $n$ подволк авчирна. Тэдгээр $n$ подволкын хэмжээ нь та ямарыг ч авчирсан болно (ижил хэмжээтэй подволк хэд хэдийг авчирсан ч болно). Ямар хэмжээний подволкуудыг авчрахыг шийдэх хүедээ та инженер бүрийн подволкны хэмжээг мэдээгүй тул Жерал найдынхаа өгсөн магадлал дээр тулгуурлан подволкуудыг сонгох хэрэгтэй болсон.

Таны даалгавар бол өөрийн хэмжээнийхээ подволкыг хүлээн авсан инженерийн тоог ихэсгэх юм.

Үүнийг илүү албан ёсоор дараах байдлаар тодорхойлбол. Та офистоо ирэх үедээ инженер бүрээс подволкны хэмжээг нь асууна. Дараагаар хэрэв танд тэр хэмжээтэй подволк байвал та түүнд өгнө. Үгүй бол та түүнд подволк өгөхгүй. Та 1-р инженерээс эхлэн асууж эхэн, дараагаар 2-р гэх мэтчилэн $n$-р инженер хүртэл явна.

Оролт

Эхний мөр харгалзан инженерүүдийн тоо, подволкуудын хэмжээнүүдийн тоог заах хоосон зайгаар тусгаарлагдсан $n, m (1 <= n <= 3000, 1 <= m <= 300)$ хоёр бүхэл тоог агуулна.

Дараагаар $n$ мөр бүр хоосон зайгаар тусгаарлагдсан $m$ тоог агуулна. $i$-р мөрийн $j$-р бүхэл тоо нь $j$ хэмжээтэй подволк $i$-р инженерт таарах магадлалыг заана. Магадлал бүр 0-с 1000-г оролцуулан хооронд нь орших бүхэл тоо. Жинхэнэ магадлал нь өгөдсөн тоог 1000-д хуваан тооцогдоно.

Инженер бүрийн хувьд бүх $m$ хэмжээтэй подволкны таарах магадлалуудын нийлбэр 1 байх нь баталгаатай.

Гаралт

Подволк авах боломжит хамгийн их инженерүүдийн тоог дүрслэх ганц бодит тоог хэвлэнэ. Хариунд $10^{-9}$ зэргийн доторх алдаа байж болно.

Орчуулсан: devman

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

Оролт
2 2
500 500
500 500
Гаралт
1.500000000000
Оролт
3 3
1000 0 0
1000 0 0
0 1000 0
Гаралт
3.000000000000
Оролт
1 4
100 200 300 400
Гаралт
0.400000000000

Тэмдэглэл

Эхний жишээнд бүх хэмжээний нэг подволк авчирна. 0.5-ийн магадлалаар хоёулаа 1 хэмжээтэй подволкт эсвэл хоёулаа хоёр хэмжээтэй подволкт аль алинд нь багтана. Өөр 0.5-ийн магадлалаар нэг инженер 1 хэмжээтэй подволкт, нөгөө нь 2 хэмжээтэй подволкт багтана. Хэрэв хамгийн эхний таамаглал зөв бол подволк авах инженерийн тоо нэг. Хэрэв хоёр дугаар таамаглал зөв бол подволк авах инженерийн тоо 2. Тиймээс подволк авах инженерүүдийн хайсан тоо маань 1.5 байна. Энэ нь подволкуудын бүх олонлогийн хувьд хамгийн их боломжит инженерүүдийн тоо юм.

Хоёр дугаар жишээний хувьд 1 хэмжээтэй подволкоос 2-ийг, 2 хэмжээтэй подволкоос нэгийг авчирна. Ингэснээр инженер бүр хэмжээнийхээ подволкыг авна.

Гурав дугаар жишээнд 4 хэмжээтэй нэг подволк авчирна.

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