B. Харанхуйн чуулга

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

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

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

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

Харанхуйн чуулга бол нөгөө ертөнцийн бодлогыг явуулдаг чуулга юм. Энд сенаторууд ирж тоглогчийн хүсэлтийн шийдвэрийг гаргадаг. Жишээ нь, дэлгүүрийн хүрээг тэлэх эсвэл хэн нэгний төрхийг сайжруулъя гэвэл Харанхуйн чуулгын зөвшөөрөл хэрэгтэй.

Харанхуйн чуулга $n$ сенартортой. Сенатор болгон тухайн тоглогчоос хамаарч $түвшин$ болон $үнэнч сэтгэл$-тэй. Түвшин нь тухайн сенаторын хүчийг илтгэнэ. Үнэнч сэтгэл нь эерэг шийдвэр гаргах магадлал бөгөөд 10%-ийн нарийвчлалтай.

Сенаторууд санал авч шийдвэр гаргадаг. Сенатор бүр эерэг эсвэл сөрөг шийдвэрийг үнэнч сэтгэлээс хамаарч гаргадаг. Хэрэв эерэг шийдвэр гаргасан сенаторуудын тоо бүх сенаторуудын тооны хагасаас их бол тоглогчийн хүсэлт биелдэг.

Хэрэв тоглогчийн хүсэлт биелээгүй тохиолдолд тоглогч Харанхуйн чуулгыг эсэргүүцэж болдог. Ингэхийн тулд тоглогч бүх сөрөг шийдвэр гаргасан сенаторуудыг утгах ёстой (сенаторуудыг устгахахд буруу зүйл байхгүй, тэд дараа нь дахин төрчихдөг ба тоглочид илүү муухай ханддаг л болно). Тоглогч грүпп сенаторуудыг устгаж болох магадлал нь $A / (A + B)$, $A$ тоглогчийн хүч, $B$ нь грүппд байгаа сенаторуудын хүчний нийлбэр. Хэрэв тоглогч хүссэн сенаторуудаа устгаж чадвал түүний хүсэлт биелнэ.

Сенаторууд чихэрэнд маш их дуртай. Тэдэнд чихэр өгч урвуулж болдог. Сенаторт чихэр өгвөл түүний тоглогчид хандах үнэнч сэтгэл 10%-иар нэмэгддэг. Үнэнч сэтгэл 100%-иас хэтрэхгүй гэдгийг дурьдъя. Тоглогч $k$ ихгүй чихрийг сенаторуудад өгч болно. Чихрийг санал авалт эхлэхийн өмнө сенаторуудад өгсөн байна.

Хэрэв чихрийг байж болох хамгийн сайнаар нь тараахад Харанхуйн чуулга тоглогчийн хүсэлтийг зөвшөөрөх магадлалыг ол.

Оролт

Эхний мөрөнд $n$, $k$ ба $A$ ($1 ≤ n, k ≤ 8$, $1 ≤ A ≤ 9999$) бүхэл тоо.

Дараагийн $n$ мөрний $i$-дахь мөрөнд эдгээр хоёр тоо байна - $b_{i}$ болон $l_{i}$ - $i$-р сенаторын түвшин болон үнэнч сэтгэлийн утга.

Бүх сенаторуудын түвшин $1$-ээс $9999$ хооронд байх ба үнэнч сэтгэл нь $0$-ээс $100$ хооронд утгаа авах бөгөөд $10$ хуваагдана.

Гаралт

Хариу болох нэг бодит тоо - $k$ чихрийг байж болох хамгийн сайнаар нь тараахад Харанхуйн чуулга тогогчийн хүсэлтийг зөвшөөрөх магадлалыг 6 оронгийн нарийвчлалтай гарга.

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

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

Оролт
5 6 100
11 80
14 90
23 70
80 30
153 70
Гаралт
1.0000000000
Оролт
5 3 100
11 80
14 90
23 70
80 30
153 70
Гаралт
0.9628442962
Оролт
1 3 20
20 20
Гаралт
0.7500000000

Тэмдэглэл

Эхний жишээнд хамгийн сайн чихэр тараахын тулд эхний гурван сенаторт тараах юм. Ингэвэл ихэнх саналыг байнга авна.

Хоёрдугаар жишээнд тоглогч тавдугаар сенаторт бүх гурван чихрээ өгөх ёстой.

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