D. Гүүгл Код Жэм

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

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

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

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

Та бүхний ихэнх нь Гүүгл Код Жэм раундын дүрмийг сайн мэддэг байх. Танд энэ бодлогыг шийдэхэд хэрэг чухал үеүүдийг сануулая. Раундын туршид оролцогчдыг хэд хэдэн бодлогыг шийдэхийг санал болгодог ба бодлого бүр хоёр дэд бодлогод хуваагдана: бага хязгаартай (бага оролттой) хялбархан, ба их хязгаартай (их оролттой) хүнд. Та уг бодлогын хялбар хувилбарыг шийдсэнийхээ дараа л хүнд хувилбарын шийдлийг илгээх боломжтой. Бодлогуудын хувьд өөр хязгаарлалтууд байхгүй. Тухайлбал оролцогч эхлээд хялбар хувилбарыг шийдчихээд өөр бодлогоруу шилжээд буцаад хүнд хувилбар дээр ирж болно. Хувилбар бүрийг шийдсэнээр оролцогчид тодорхой хэмжээний оноо өгнө (ихэнхдээ бодлого бүрийн хувьд ялгаатай). Уг оноог авахдаа тухайн хувилбарт зориулсан бүх тест дээр зөв ажилснаар авна. Оролцогч хялбар хувилбарын тестийн хариуг шийдлээ илгээснийхээ яг дараа нь хүлээж авдаг бол хүнд хувилбарын тестийн хариу зөвхөн раунд дууссаны дараа л гардаг. Эцэст нь оролцогчид авсан онооныхоо өсөх эрэмбээр хүснэгтэнд жагсдаг. Хэрвээ оноо тэнцсэн бол торгуульт хугацаагаараа эрэмбэлэгддэг. Гүүгл од Жэмийн дүрмүүдийн дагуу энэ хугацаа нь хамгийн сүүлийн зөв шийдэл илгээсэн хугацаа байдаг.

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

  • $i$-р бодлогын хялбар хувилбарыг бодсоноор оролцогч $scoreSmall_{i}$ оноо авах бол хүнд хувилбарыг бодсоноор илүү $scoreLarge_{i}$ оноо авна. Таны $i$-р бодлогоос авч болох хамгийн их оноо нь $scoreSmall_{i} + scoreLarge_{i}$.
  • Васягийн хувьд $i$-р бодлогын хялбар хувилбарыг шийдэхдээ яг $timeSmall_{i}$ минут зарцуулна. Уг кодоо сайжруулаад хүнд хэлбэрийн шийдэл болгохын тулд дахиад $timeLarge_{i}$ минут зарцуулна.
  • Вася туршлагатай учир бүх хялбар хэлбэрийн бодлогуудыг эхний оролдлогоор шийднэ. Харин хүнд хэлбэрийн бодлогууд тийм ч амар биш ба раундын төгсгөлд хүнд хэлбэрийн бодлогын шийдэл болгож илгээсэн шийдэл буруу байх магадлал нь $probFail_{i}$ байна. Эдгээр шийдлүүд нь оролцогчдын оноо болон торгуульт хугацаанд нөлөөлөхгүй.

Раунд $t$ минут үргэлжилдэг. Бодлогуудыг унших болон шийдлүүдийг илгээхэд цаг зарцуулахгүй гэж үзнэ. Вася раунд яг дуусах мөчид шийдэл илгээх боломжтой.

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

Оролт

Эхний мөрөнд хоёр бүхэл тоо $n$ ба $t$ ($1 ≤ n ≤ 1000, 1 ≤ t ≤ 1560$) байна. Дараагийн $n$ мөр бүрт 5 тоо: $scoreSmall_{i}, scoreLarge_{i}, timeSmall_{i}, timeLarge_{i}, probFail_{i}$ ($1 ≤ scoreSmall_{i}, scoreLarge_{i} ≤ 10^{9}, 1 ≤ timeSmall_{i}, timeLarge_{i} ≤ 1560, 0 ≤ probFail_{i} ≤ 1$) байна.

$probFail_{i}$ нь бодит тоо ба цэгээс хойш хамгийн ихдээ 6 цифр агуулна. Бусад бүх тоо нь бүхэл тоо байна.

Гаралт

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

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

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

Оролт
3 40
10 20 15 4 0.5
4 100 21 1 0.99
1 4 1 1 0.25
Гаралт
24.0 18.875
Оролт
1 1
100000000 200000000 1 1 0
Гаралт
100000000 1

Тэмдэглэл

Эхний жишээн дээр бодлогуудыг шийдэх хамгийн оновчтой дараалал нь:

  1. Гуравдугаар бодлогын хялбар хувилбар.
  2. Нэгдүгээр бодлогын хялбар хувилбар.
  3. Гуравдугаар бодлогын хүнд хувилбар.
  4. Нэгдүгээр бодлогын хүнд хувилбар.

Хэрвээ та гуравдугаар бодлогын хоёр хувилбарын оронд хоёрдугаар бодлогын хялбар хувилбарыг шийдвэл таамаглалт нийт оноо нь ижил байх боловч таамаглалт торгуульт цаг ($38$) нь их байна.

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