B. Мөөг Ургуулах Тэмцээн

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

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

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

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

Одойчуудын улсад жил бүр мөөг ургуулах тэмцээн болдог.

Тэмцээнд оролцогч бүр өөрийн гэсэн ургуулах мөөгтэй/эхний өндөр 0/ байдаг ба тэмцээний дүрэм ёсоор тэмцээн нь хоёр үе бүрддэг. Эхний үе нь $t_1$ секунд, хоёрдох үе нь $t_2$ секунд үргэлжилдэг ба хоёр үеийн дунд нь богинохон завсарлага байдаг.

Шүгэл дугарсны дараа оролцогчид мөөгнүүдээ $v_i$ метр/секундын хурдтайгаар ургуулж эхлэдэг бөгөөд $t_1$ секундын дараа завсарлага эхлэдэг. Завсарлагын үеээр бүх мөөгнүүд $k$ хувиар намхан болдог. Завсарлагааны дараагаар оролцогчид мөөгнүүдээ үргэлжлүүлэн $u_i$ хурдтайгаар ургуулцгааж эхлэдэг ба $t_2$ секундын дараа тэмцээн дуусдаг. Завсарлагааны өмнөх болон дараах хурдууд ялгаатай байж болохыг анхаарна уу.

Тэмцээний өмнө одой Паша оролцогч бүрээс асуун тэд хүн бүр ямар ямар хоёр хурд хэрэглэхий нь олж мэдсэн боловч хоёр хурдаа ямар дарааллаар хэрэглэхий нь мэдэж чадсангүй. Өөрөөр хэлвэл ямар нэгэн оролцогч $a_i$ ба $b_i$ хурдтай байлаа гэхэд $a_i$ хурдаа завсарлагааны өмнө хэрэглээд $b_i$ хурдаа завсарлагааны дараа хэрэглэх юм уу эсвэл эсрэгээрээ юу гэдэг нь мэдэгдэхгүй байгаа.

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

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

Оролт

Эхний мөрөнд оролцогчдын тоо $n$, завсарлагааны өмнөх үеийн үргэлжлэх хугацаа $t_1$, завсарлагааны дараах үеийн үргэлжлэх хугацаа $t_2$, завсарлагааны үеээр мөөгнүүдийн намхан болох хувь $k(1<=n, t_1, t_2<=1000; 1<=k<=100)$ гэсэн 4 бүхэл тоо байрлана.

Дараагийн $n$ ширхэг мөрөнд хоёр бүхэл тоонууд байрлах ба $i$-р мөрөндөх $a_i, b_i(1<=a, b <=1000)$ тоонууд нь $i$-р оролцогчийн хэрэглэх хурдуудыг илэрхийлнэ.

Гаралт

$n$ мөр бүхий хариуны хүснэгтийг хэвлэ. Мөр болгонд харгалзах оролцогчийн дугаар, ургуулсан мөөгнийх эцсийн өндөр нь хоёр орны нарийвчлалтайгаар байрлана.

Орчуулсан: devman

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

Оролт
2 3 3 50
2 4
4 2
Гаралт
1 15.00
2 15.00
Оролт
4 1 1 1
544 397
280 101
280 101
693 970
Гаралт
4 1656.07
1 937.03
2 379.99
3 379.99

Тэмдэглэл

  • First example: for each contestant it is optimal to use firstly speed 2 and afterwards speed 4, because $230.5 + 43 > 430.5 + 23$.
Сэтгэгдлүүдийг ачааллаж байна...