C. Хоёр дахь үнийн өрсөлдөөн

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

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

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

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

Одоо үед интернет сурталчилгаануудын ихэнх нь вэб хуудасруу статикаар холбогдоогүй байдаг. Үүний оронд вэб хуудсыг нээж байгаа хүнд юу харагдах нь вэб хуудас нээгдсэний дараа 100 миллсекундэд тодорхойлогддог. Ихэвчлэн хэд хэдэн компаниуд вэб хуудсан дээрх зар сурталчилгааны зай бүр дээр үнэ хаялцах маягаар өрсөлддөг. Компани бүр хэрэглэгч болон вэб хуудас, зар сурталчилгааны зайн талаар дэлгэрэнгүй мэдээлэл агуулсан хүсэлт хүлээн авна. Тэд уг зар сурталчилгааны зайн дээр сурталчилгаагаа тавихад төлөх үнийн саналаа 100 миллсекундэд багтаан хариу илгээх ёстой. Хамгийн өндөр үнэ санал болгосон компани уг зайн дээр сурталчилгаагаа байршуулна. Хэрвээ хамгийн өндөр үнэтэй тэнцсэн хэд хэдэн компани байвал ялагч нь санамсаргүйгээр сонгогдоно.

Гэсэн хэдий ч үнийн өрсөлдөөнд ялсан компани үнийн саналтайгаа тэнцүү хэмжээний мөнгө төлж чаддаггүй. Ихэнх тохиолдолд хоёр дахь үнийн өрсөлдөөнийг ашигладаг. Энэ нь компаний төлсөн мөнгөний хэмжээ нь тухайн зар сурталчилгааны зай дээр тавигдсан бусад үнийн саналуудын хамгийн ихтэй нь тэнцэнэ гэсэн үг.

Иймэрхүү нэг үнэ хаялцах үйл явцыг авч үзье. Зар сурталчилгаа байрлуулахаар $n$ компани өрсөлдөж байна гэе. $i$-р компаний үнийн санал нь $L_{i}$ ба $R_{i}$ тоонуудыг оролцуулан энэ хоёр тооны хоорондох бүхэл тоонуудаас тэнцүү магадлалтайгаар санамсаргүй сонгосон тоотой тэнцүү микродолларын санал байна. Өөрөөр хэлбэл $i$-р компаны үнийн саналын утга нь $[L_{i}, R_{i}]$ хүрээнээс тэнцүү магадлалтайгаар сонгосон дурын бүхэл тоо байж болно гэсэн үг.

Ялагч хоёр дахь үнийн өрсөлдөөнд төлөх мөнгөний дундаж утгыг тодорхойл.

Оролт

Оролтын эхний мөрөнд бүхэл тоон утга $n$ ($2 ≤ n ≤ 5$) байна. Дараа нь $n$ мөр байх ба эдгээр мөрүүдийн $i$-р мөр бүрт хоёр тоо $L_{i}$ ба $R_{i}$ ($1 ≤ L_{i} ≤ R_{i} ≤ 10000$) байх буюу $i$-р компаны үнийн саналын хязгаарууд юм.

Энэ бодлогонд дэд бодлогууд байхгүй. Таны хянуулахаар өгсөн шийдэл зөв байвал та 8 оноо авна.

Гаралт

Үнэмлэхүй болон харьцангуй алдаа нь $1e - 9$-с ихгүй хариултыг хэвлэ.

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

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

Оролт
3
4 7
8 10
5 5
Гаралт
5.7500000000
Оролт
3
2 5
3 4
1 6
Гаралт
3.5000000000

Тэмдэглэл

Эхний жишээг авч үзье. Эхний компани $[4, 7]$ хүрээнээс санамсаргүй сонгосон бүхэл тоотой тэнцүү микродоллар бүхий үнийн санал илгээнэ; хоёр дахь компани $8$-с $10$-н хооронд үнийн санал илгээх бол гурав дахь компани $5$ микродолларын үнийн санал илгээнэ. Хоёр дахь компани ямар үнийн санал илгээхээсээ үл хамааран ялна, гэсэн хэдий ч түүний төлөх мөнгө нь эхний компаны үнийн саналаас хамаарна. $0.5$ магадлалтайгаар эхний компани хамгийн ихдээ $5$ микродолларын үнийн санал ирүүлэх ба өрсөлдөөний хамгийн их хоёр дахь үнэ нь $5$ байна. Эхний компани $0.25$ магадлалтайгаар $6$ микродолларын үнийн санал ирүүлэх ба $0.25$ магадлалтайгаар $7$ микродолларын үнийн санал ирүүлнэ. Ингээд хоёр дахь компаны төлөх дундаж утга нь $0.5*5 + 0.25*6 + 0.25*7 = 5.75$ байна.

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