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

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.

The first line contains two integers **n** and **r** (**1** ≤ **n,r** ≤ **10 ^{6}**) — the number of monsters and the blast radius of the spell.

Next **n** lines contain an integer **x _{1}**,

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

Input | Output |
---|---|

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

66% Solution Ratio

Anika_TabusshuEarliest,

prodip_bsmrstuFastest, 0.0s

RAKIBULHOSSAINLightest, 1.0 MB

Umme.RukayaShortest, 565B

Login to submit