Codeforces Round #804 (Div. 2)
00:13:24 |
Educational Codeforces Round 131 (Rated for Div. 2)
5 өдрийн дараа |
Codeforces Round #805 (Div. 3)
7 өдрийн дараа |
Codeforces Round #806 (Div. 4)
9 өдрийн дараа |
E. Баавгай ба парадокс
хугацааны хязгаарлалт 3.5 секунд
санах ойн хязгаарлалт 256 мегабайт
оролт стандарт оролт
гаралт стандарт гаралт
Лимак бол том цагаан баавгай. Тэр алгоримтын тэмцээнд $n$ ширхэг бодлого бэлджээ. $i$ дэх бодлого анхлан $p_{i}$ оноотой байна. Мөн шалгагчийн хэлснээр $i$ дэх бодлогыг бодоход $t_{i}$ минут зарцуулах аж. Бодлогууд хүндрэлийн түвшнээрээ эрэмбэлэгдээгүй ба магадгүй хүндэвтэр бодлогууд эхэндээ харьцангуй бага оноотой ч байж болно. Лимак анхдагч оноогоо аль эрт зарлачихсан тул өөрчлөхөд нэгэнт оройтсон байв. Гэсэн ч бодлогууд оноо алдах хурд буюу $c$-г тохируулах боломжтой хэвээр.
Бүх бодлогыг бодоход шаардлагатай хугацааг $T$ гэе. (ө.х $T = t_{1} + t_{2} + ... + t_{n}$). Тэмцээн $T$ үргэлжилнэ. Иймд бүх бодлогоо амжиж бодох боломжтой.
Бодлого бодоход өгөх оноо нь шугаман байдлаар буурна. $i$-р бодлогыг тэмцээн эхэлснээс хойш $x$ минутанд бодвол яг оноо авна. Энд
нь Лимакийн сонгох бодит тоо.
$c$ тоог бэхлэгдсэн гэж үзье. Тэмцээний үеэр оролцогч бодлогуудаа ямар дарааллаар бодохоо шийднэ. Нийт $n!$ боломжит дараалал байх ба тус бүрдээ ямар нэгэн оноо өгнө. (бүхэл байх албагүй) Хамгийн өндөр оноо өгөх дарааллыг оптимал гэнэ. Өөрөөр хэлбэл энэ дарааллаас авах оноо өөр ямар ч дарааллаас хүртэх онооноос багагүй байна. Ядаж нэг оптимал дараалал байх нь ойлгомжтой. Харин нэгээс олон байх боломжтой.
Оролцогч тэмцээний эхэнд $t_{i}$ цагаа зөв тооцож оптимал дараалал сонгоно, мөн шалгагчид ч бодлогууд бодогдох хугацааг зөв таамагласан гэж үзэж буй.
$p_{i} < p_{j}$ байх ялгаатай $i$, $j$ бодлогуудын хувьд оролцогч $i$ бодлого дээр $j$-ээс өндөр авахад Лимак таагүй хандах ба ийм нөхцөл байдлыг тэрээр парадокс гэж нэрлэжээ.
$c = 0$ тохиолдолд ямар ч парадокс үүсэхгүй нь ойлгомжтой. Харин том $c$-н хувьд нөхцөл байдал арай ээдрээтэй. Ямар ч паракдокс үл үүсэх хамгийн их $c$-г ( болохыг санаарай) олно уу, өөрөөр хэлбэл ямар ч оптимал дарааллын хувьд нэг ч парадокс оршихгүй байх хамгийн их $c$-г тогтооно уу.
Нөхцөлийг хангах $c$ үргэлжид оршин байхыг баталж болно.
Оролт
Эхний мөрөнд бодлогуудын тоог илтгэх $n$ ($2 \le n \le 150 000$) тоо өгөгдөнө.
Хоёр дах мөрөнд $n$ ширхэг анхдагч оноонууд өгөгдөнө: $p_{1}, p_{2}, ..., p_{n}$ ($1 \le p_{i} \le 10^{8}$).
Гурав дах мөрөнд $n$ ширхэг $t_{1}, t_{2}, ..., t_{n}$ ($1 \le t_{i} \le 10^{8}$) тоонууд өгөгдөх ба $t_{i}$ нь $i$-р бодлогыг бодоход шаардагдах хугацааг илэрхийлнэ.
Гаралт
$c$-н хамгийн их утга болох бодит тоог хэвлэ. and there is no optimal order with a paradox.
Зөрүү нь $10^{ - 6}$ дотор байвал хариуг зөвд тооцно.
Хэрэв таны хариу $a$, зохиогчийн хариу $b$ байвал дараах нөхцөлд л шалгах програм таны хариуг зөвд тооцно:.
Орчуулсан: Төрбат
Жишээ тэстүүд
Оролт
3 4 3 10 1 1 8
Гаралт
0.62500000000
Оролт
4 7 20 15 10 7 20 15 10
Гаралт
0.31901840491
Оролт
2 10 20 10 1
Гаралт
1.00000000000
Тэмдэглэл
Эхний жишээнд $3$ бодлого өгөгдөнө. Эхнийх нь $(4, 1)$ (анхдагч оноо $4$ ба бодоход $1$ минут шаардана), хоёр дах бодлого $(3, 1)$ ба гурав дах бодлого $(10, 8)$. Нийт хугацаа $T = 1 + 1 + 8 = 10$.
$c = 0.7$ үед парадокс үүсэхийг харуулъя. $1$, $2$, $3$ дарааллаар бодох нь хамгийн их оноог өгнө:
- Эхэлснээс хойш $1$ минутын дараа бодно:
- Эхэлснээс хойш $2$ минутын дараа бодно:
- Эхэлснээс хойш $10$ минутын дараа бодно:
Иймд энэ дараалал $3.72 + 2.58 + 3 = 9.3$ оноо өгөх (Нөгөө $5$ боломжит дарааллыг шалгаж болох ба үүнээс бага оноо өгнө) ба $1$, $3$ бодлогуудын хувьд парадокс үүснэ. $4 < 10$ боловч $3.72 > 3$ байх тул парадокс юм. Цаашилбал $c = 0.625$ тохиолдолд ямар ч парадокс үл үүсэх ба үүнээс $c$ бүрийн хувьд парадокс үүсэх юм.
Хоёр дах жишээнд $24$ дараалал бүгд оптимал.
Гурав дах жишээнд $c = 1$ байхад ч парадокс үүсэхгүй.