Masala #0624
Duck Hunting 2D GAME
Duck Hunting 2D GAME o'yinida ovchi o'rdak ovlashi kerak bo'ladi. O'yin 2D ya'ni ikki o'lchamli koordinatada bo'lib o'tadi.
Ovchi \((0,0)\) koordinatada joylashgan, u faqat vertikal ravishda miltiqdan o'q uzadi. Vertikal uzilgan o'q osmondagi o'rdakni yaralasa ovchining qo'liga kelib tushadi. Dastlab osmonda jami bo'lib \(N\) ta o'rdak bor va har bir uzilgan o'qdan so'ng ovchi miltiqni qayta o'qlashi uchun \(R\) soniya vaqt sarflaydi. Barcha o'rdaklar \(Ox\) o'qiga nisbatan teskari ya'ni manfiy yo'nalishda harakat qilmoqda, sizga har bir o'rdakning \(Ox\) o'qiga nisbatan qaysi oraliqda uchayotgani beriladi. Har bir o'rdak 1 soniyada \(Ox\) o'qiga nisbatan chap tomonga bir birlik siljiydi.
O'rdak uchayotgan balandlik muhim emas chunki miltiqdan otilgan o'q cheksiz balandlikka ko'tariladi va yo'lidagi barcha o'rdaklarni yaralaydi(dastlab miltiq o'qlangan).
Kirish faylining dastlabki satrida \(N,R(1\leq N\leq 200, 1\leq R\leq 10^9)\) mos ravishda o'rdaklar soni va miltiqni qayta o'qlashi uchun ketadigan vaqt. Kiyingi \(N\) ta satrda \(x1_i,x2_i(-10^9\leq x1\leq x2\leq10^9)\) juftliklar \(i-\)o'rdak qaysi oraliqda ekanligi.
Chiqish faylida optimal o'ynaydigan o'yinchi ko'pi bilan qancha o'rdakni ovlay olishini chop eting.
| # | input.txt | output.txt |
|---|---|---|
| 1 |
3 3 -3 0 1 3 -1 2 |
3 |
1-test:
Ushbu test rasimda tasvirlangan optimal o'ynaydigan o'yinchi \(1-\)chi va \(3-\)chi o'rdaklarni bir o'q bilan urib tushiradi(ikkalasixam \(0\) nuqtadan uchishni boshlagan) va miltiqni qayta o'qlash uchun \(3\) soniya vaqt sarflab \(2-\)chi o'rdakni yaralaydi(\(2-\)chi o'rdak \(3\) nuqtadan uchishni boshlagan).
Shuni unitmanki \(i-\)chi o'rdak \([x1_i, x2_i]\) oraliqning istalgan butun nuqtasidan uchishni boshlagan deb qarashingiz mumkun.
Telegram kanalimizga obuna bo'ling