Masala #0624

Xotira 16 MB Vaqt 1000 ms Qiyinchiligi 40 %

3.5 (Baholar 6)

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.

sample-img

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).

Kiruvchi ma'lumotlar:

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.

Chiquvchi ma'lumotlar:

Chiqish faylida optimal o'ynaydigan o'yinchi ko'pi bilan qancha o'rdakni ovlay olishini chop eting.

Misollar

#	input.txt	output.txt
1	3 3 -3 0 1 3 -1 2	3

Izoh:

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 Facebook

Yechimini yuborish

Bu amalni bajarish uchun tizimga kiring, agar profilingiz bo'lmasa istalgan payt ro'yxatdan o'tishingiz mumkin