Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Déjà Vu

By backbencher16 · Limits 1s, 512 MB

Thor, the Thunder God is fighting a horde of monsters in a cave. The cave is so narrow that it can be represented as an infinite coordinate line. Monsters are standing in positive integer coordinate points. Thor can cast spells at any integer point while flying. The spell has a blast radius, r. Suppose, Thor has cast a spell at point c. Let some monster’s current coordinate be y, now:

if y<=0, the monster is killed.

if c==y, the monster is killed.

if c>y and c-y<=r, the monster is pushed r units to the left, so its current coordinate becomes y−r.

if c<y and y-c<=r, the monster is pushed r units to the right, so its current coordinate becomes y+r.

Casting spells drains a lot of energy, so he wants to know the minimum number of spells he needs to cast to kill all the monsters.

Input

The first line contains two integers n and r (1n,r106) — the number of monsters and the blast radius of the spell.

Next n lines contain an integer x1, x2, …, xn ( 1x1..n106) — the initial positions of the monsters.

Output

Print the minimum number of spells he needs to cast to kill all the monsters.

Sample

InputOutput
4 1
5 
2
3
5
3

There are monsters at points 2,3 and 5. Thor casts a spell at point 5 and kills the two monsters. He casts a spell at point 3, thus kills the monster at point 3 and pushed the monster at point 2 to point 1. He casts a spell at point 1 and kilsl the last monster. As a result, he needed 3 spells.



Discussion
Statistics

62% Solution Ratio

Anika_TabusshuEarliest, 3w ago

prodip_bsmrstuFastest, 0.0s

RAKIBULHOSSAINLightest, 1.0 MB

Umme.RukayaShortest, 565B

Submit

Login to submit