Masala #1033
Kill the monsters!
“Kill the monsters!” nomli o‘yin mavjud. Bu o‘yinda, siz tushunib ulgurganingizdek, monsterlar bor va ularni o‘ldirish lozim.
O‘yin maydoni bitta uzun kesma bo‘lib, u \(-10^9\) dan \(10^9\) gacha raqamlangan koordinatalardan iborat. Koordinata 3 xil holatda bo‘lishi mumkin: koordinata bo‘sh, koordinatada 1 ta monster bor yoki koordinatada 1 ta devor bor. Maydondagi jami devorlar va monsterlar soni \(n\) ga teng. Har bir monster o‘zining sog‘lik darajasiga ega.
Siz \(k\) marta quyidagi ishni qila olasiz:
- o‘yin maydonida devor bo‘lmagan va oldin belgilanmagan koordinatani tanlash va uni belgilash
So‘ng barcha belgilangan koordinatalarda bir vaqtda olov yoqasiz.
Qaysidir koordinatada olov yongan bo‘lsa, 1 soniyada shu koordinatadagi monsterning sog‘lik darajasi 1 birlikka kamayadi, hamda olov oldin yonmagan va devori yo‘q bo‘lgan qo‘shni koordinataga ham o‘tadi. Olov yongan koordinatada u hech qachon o‘chmaydi. Monsterning sog‘lik darajasi 0 ga tushsa, u o‘ldi deb hisoblanadi.
Yondirish uchun \(k\) ta koordinatani optimal tanlab ularni yondirgach, eng kami bilan necha soniyadan so‘ng barcha monsterlar o‘lishini toping.
Optimal tanlovda ham, \(10^{100}\) soniyadan so‘ng tirik monster topilsa, “IMPOSSIBLE” so‘zini qo‘shtirnoqlarsiz chiqaring.
Kirish oqimining birinchi qatorida ikkita butun sonlar - \(n,k(1 \le k \le n \le 2*10^5)\) kiritiladi.
Keyingi \(n\) ta qatorning har birida maydondagi bo‘shmas kataklar ko‘rsatiladi.
Monster uchun yangi qatorda ‘M’ belgisi va yana 2 ta butun son - \(x(-10^9 \le x \le 10^9)\) monster turgan koordinata va \(h(1 \le h \le 10^9)\) monsterning sog‘lik darajasi kiritiladi.
Devor uchun yangi qatorda ‘W’ belgisi va yana 1 ta butun son - \(x(-10^9 \le x \le 10^9)\) devor turgan koordinata kiritiladi.
Barcha testlar tepadagi shartlarni qanoatlantirishi kafolatlanadi.
Yagona qatorda masala javobini chiqaring.
| # | input.txt | output.txt |
|---|---|---|
| 1 |
3 2 M 1 4 W 2 M 3 6 |
6 |
| 2 |
3 1 M 1 4 W 2 M 3 6 |
IMPOSSIBLE |
| 3 |
2 1 M -1000000000 1 M 1000000000 2 |
1000000002 |
Birinchi testda:
- 1 koordinatada sog‘ligi 4 bo‘lgan monster bor.
- 2 koordinatada devor bor.
- 3 koordinatada sog‘ligi 6 bo‘lgan monster bor.
Yondirish uchun 2 ta koordinatani belgilash lozim. 1 va 3 koordinatani belgilab ularni yondirsak, 6 soniyada barcha monsterlar o‘ladi. Bu eng yaxshi natija ekanligini isbotlasa bo‘ladi.
Ikkinchi testda:
Devor va monsterlar xuddi birinchi testdagidek, yagona farqi yondirish uchun faqatgina 1 ta koordinatani tanlash mumkin. Bu holatda javob “IMPOSSIBLE”. Chunki qaysi koordinatani yondirmaylik, bitta monster o‘ladi, boshqa monster esa devor sababli \(10^{100}\) soniyadan so‘ng ham tirik qoladi.
Uchinchi testda:
Faqatgina 1 ta koordinatani yondirish mumkin. 0 koordinatani tanlash optimal bo‘ladi. Bunda 1-monsterga yetib olib uni o‘ldirish uchun \(10^9+1\) soniya vaqt kerak. 2-monsterga yetib olib uni o‘ldirish uchun esa \(10^9+2\) soniya vaqt kerak. Jami \(10^9+2\) soniyadan so‘ng barcha monsterlar o‘lgan bo‘ladi.
Telegram kanalimizga obuna bo'ling