OTHS Coding Competition 1 (Mock CCC) J3 - Explosion

View as PDF

Submit solution

Points: 5 (partial)
Time limit: 1.0s
Memory limit: 512M

Problem type

After buying a new wand, Megumin wants to test it out on some bombs. She finds N bombs lined up in a row. The i^{th} bomb is on a tower h_i meters high. A bomb explodes when Megumin manually detonates it or when an adjacent bomb with a height difference of less than or equal to D explodes. How many bombs does Megumin need to manually detonate for all bombs to explode? Additionally, among all shortest ways to detonate all bombs, what is the largest single chain reaction that can be created?


1 \le N \le 10^6

1 \le h_i \le 1000

0 \le D \le 1000

Subtask 1 [5/15]

1 \le N \le 2000

Subtask 2 [10/15]

No additional constraints.

Input Specification

The first line of input contains 2 integers, N, the number of bombs, and D, the maximum difference in height allowed for a bomb to set off an adjacent bomb.

The second line of input contains N space separated integers, h_i, the height of each bomb.

Output Specification

On the first line, output a single integer, the number of bombs Megumin needs to manually detonate for all bombs to explode.

On the second line, output a single integer, the largest explosion (in terms of count) that can be created from manually detonating a single bomb.

Sample Input

8 3
10 7 5 9 1 1 7 10

Sample Output


Explanation for Sample Output 1

In total, Megumin needs to set off 4 bombs for everything to explode. One way to do this is setting off bombs 1, 4, 5, and 7.

The largest explosion can be created by setting off bomb 1, this will set off bomb 2 since |10-7| \le 3, which sets off bomb 3 since |7-5| \le 3. In total, 3 bombs exploded from setting off a single bomb.


There are no comments at the moment.