Masala #0292
Kuzatuv kamerasi
Baytlandiya mamlakati bir o’lchovli kesmada joylashgan. Unda jami N ta xonadon mavjud. Har bir xonadon sonlar o’qidan qaysidir bir koordinatada joylashgan. Baytlandiya qiroli o’z davlatidagi barcha xonadonni kuzatib turish uchun mamlakat bo’ylab kameralar o’rnatishga qaror qildi. Har bir kamera mamlakatdagi qaysidir bir xonadonning tomiga o’rnatiladi, va o’rnatilgan koordinatasidan turib K masofani kuzata oladi. Mamlakatdagi barcha xonadonni kuzata olishi uchun Baytlandiya qiroliga eng kamida nechta kamera kerak bo’lishini aniqlang.
Kirish faylining birinchi satrida ikkita butun son, N va K (1 ≤ N, K ≤ 105) sonlari kiritiladi. Ikkinchi satrida N ta [1, 105] oralig’idagi butun son, har bir xonadon joylashgan koordinata kiritiladi.
Chiqish faylida yagona butun son, mamlakatdagi barcha xonadonni kuzata olishi uchun Baytlandiya qiroliga eng kamida nechta kamera kerakligini chop eting.
# | input.txt | output.txt |
---|---|---|
1 |
5 1 1 2 3 4 5 |
2 |
2 |
8 2 7 2 4 6 5 9 12 11 |
3 |
1-test:
2-test: