CCROSSX - Cross Mountain Climb Extreme

no tags 

Somewhere in the neighborhood we have a very nice mountain that gives a splendid view over the surrounding area. There is one problem though: climbing this mountain is very difficult, because of rather large height differences. To make more people able to climb the mountain and enjoy the view, we would like to make the climb easier. To do so, we will model the mountain as follows: the mountain consists of n adjacent stacks of stones, and each of the stacks is hi high. The successive height differences are therefore hi+1 − hi (for 1 ≤ i ≤ n−1). We would like all absolute values of these height differences to be smaller than or equal to some number d.

We can do this by increasing or decreasing the height of some of the stacks. The first stack (the starting point) and the last stack (the ending point) should remain at the same height as they are initially. Since adding and removing stones requires a lot of effort, we would like to minimize the total number of added stones plus the total number of removed stones. What is this minimum number?


On the first line one positive number: the number of test cases, at most 50. After that, for each test case:

  • One line with two integers n (2 ≤ n ≤ 10000) and d (0 ≤ d ≤ 10^9): the number of stacks of stones and the maximum allowed height difference.
  • One line with n integers hi (0 ≤ h≤ 10^9): the heights of the stacks.


For each test case, output one line with the minimum number of stones that have to be added or removed, or “impossible” if it is impossible to achieve the goal.


10 2
4 5 10 6 6 9 4 7 9 8
3 1
6 4 0
4 2
3 0 6 3


Added by:Lovro Puzar
Time limit:0.400s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:Problem CCROSS with larger limits (originally from NWERC 2008)