Masala #0292

Xotira 16 MB Vaqt 1000 ms

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.

Kiruvchi ma'lumotlar:

Kirish faylining birinchi satrida ikkita butun son, N va K (1 ≤ N, K ≤ 10⁵) sonlari kiritiladi. Ikkinchi satrida N ta [1, 10⁵] oralig’idagi butun son, har bir xonadon joylashgan koordinata kiritiladi.

Chiquvchi ma'lumotlar:

Chiqish faylida yagona butun son, mamlakatdagi barcha xonadonni kuzata olishi uchun Baytlandiya qiroliga eng kamida nechta kamera kerakligini chop eting.

Misollar

#	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

Izoh:

1-test:

k-nearest(2).png

2-test:

k-nearest2(2).png