There is a big staircase with $N$ steps (numbered $1$ through $N$) in ChefLand. Let's denote the height of the top of step $i$ by $h_i$. Chef Ada is currently under the staircase at height $0$ and she wants to reach the top of the staircase (the top of the last step). However, she can only jump from height $h_i$ to the top of a step at height $h_f$ if $h_f-h_i \le K$. To help Ada, we are going to construct some intermediate steps; each of them may be constructed between any two steps, or before the first step, and have any height. What is the minimum number of steps that need to be added to the staircase so that Ada could reach the top?

-----Input-----
- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
- The first line of each test case contains two space-separated integers $N$ and $K$.
- The second line contains $N$ space-seperated integers $h_1, h_2, \dots, h_N$.

-----Output-----
For each test case, print a single line containing one integer — the minimum required number of steps.

-----Constraints-----
- $1 \le T \le 64$
- $1 \le N \le 128$
- $1 \le K \le 1,024$
- $1 \le h_i \le 1,024$ for each valid $i$
- $h_i < h_{i+1}$ for each valid $i$

-----Example Input-----
1
4 3
2 4 8 16

-----Example Output-----
3

Source: codechef | Difficulty: EASY
Tags: Mathematics

Implementation


Solutions:
import numpy as np

def minstairs(n, k):
	stairsHeight = []
	stairs = 0
	current = 0
	stairsHeight = list(map(int, input().split()))
	stairsHeight = np.array(stairsHeight)
	curr = 0
	for i in range(n):
		if stairsHeight[i] - curr <= k:
			curr = stairsHeight[i]
		else:
			if (stairsHeight[i] - curr) % k == 0:
				stairs += (stairsHeight[i] - curr) // k - 1
			else:
				stairs += (stairsHeight[i] - curr) // k
			curr = stairsHeight[i]
	return stairs
T = int(input())
for i in range(T):
	(n, k) = list(map(int, input().split()))
	print(minstairs(n, k))


for _ in range(int(input())):
	(N, K) = map(int, input().split())
	h = list(map(int, input().split()))
	h.insert(0, 0)
	c = 0
	for i in range(1, N + 1):
		c += (h[i] - h[i - 1] - 1) // K
	print(c)


for _ in range(int(input())):
	(n, k) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	c = 0
	s = 0
	for i in range(n):
		s += (a[i] - c - 1) // k
		c = a[i]
	print(s)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	h = [int(x) for x in input().split()]
	(hf, c) = (0, 0)
	for i in h:
		if i - hf > k:
			c += (i - hf - 1) // k
		hf = i
	print(c)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	a = 0
	b = 0
	for i in range(n):
		if l[i] - b > k:
			a += (l[i] - b) // k
			if (l[i] - b) % k == 0:
				a -= 1
		b = l[i]
	print(a)


for _ in range(int(input())):
	(x, y) = map(int, input().split())
	h = list(map(int, input().split()))
	h.insert(0, 0)
	c = 0
	for i in range(1, x + 1):
		c += (h[i] - h[i - 1] - 1) // y
	print(c)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	x = [0] + list(map(int, input().split()))
	ans = 0
	for i in range(1, n + 1):
		if x[i] - x[i - 1] > k:
			ans += (x[i] - x[i - 1] - 1) // k
	print(ans)


for _ in range(int(input())):
	(n, k) = list(map(int, input().split()))
	arr = list(map(int, input().split()))
	res = (arr[0] - 1) // k
	for i in range(1, len(arr)):
		res += (arr[i] - arr[i - 1] - 1) // k
	print(res)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	sum = 0
	prev = 0
	for i in range(n):
		if l[i] - prev > k:
			sum += (l[i] - prev - 1) // k
		prev = l[i]
	print(sum)


from math import *
import sys

def input():
	return sys.stdin.readline().replace('\n', '').strip()
sys.setrecursionlimit(10 ** 9)
for _ in range(int(input())):
	(n, k) = list(map(int, input().split()))
	l = [0] + list(map(int, input().split()))
	n += 1
	ans = 0
	for i in range(1, n):
		ans += (l[i] - l[i - 1] - 1) // k
	print(ans)


for i in range(int(input())):
	(n, k) = list(map(int, input().split()))
	arr = list(map(int, input().split()))
	a = 0
	c = []
	b = []
	for i in range(n):
		m = arr[i] - a
		if k >= m:
			pass
		elif m % k == 0:
			c.append(int(m / k) - 1)
		else:
			b.append(int(m / k))
		a = arr[i]
	print(sum(c) + sum(b))


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	steps = list(map(int, input().split()))
	steps_to_add = 0
	ada_height = 0
	if max(steps) <= k:
		print(0)
	else:
		for step in steps:
			jump = step - ada_height
			if jump > k:
				steps_to_add += (jump - 1) // k
			ada_height = step
		print(steps_to_add)


for _ in range(int(input())):
	Ans = 0
	(N, K) = map(int, input().split())
	H = list(map(int, input().split()))
	for i in range(N):
		if i == 0 and K < H[i]:
			Ans = Ans + (H[i] - 1) // K
		elif K < H[i] - H[i - 1] and i > 0:
			Ans = Ans + (H[i] - H[i - 1] - 1) // K
	print(Ans)


t = int(input())
for _ in range(0, t):
	(n, k) = map(int, input().split())
	x = list(map(int, input().split()))
	x.insert(0, 0)
	j = 0
	for i in range(0, n):
		d = x[i + 1] - x[i]
		if d > k:
			if d % k != 0:
				j = j + d // k
			else:
				j = j + d // k - 1
	print(j)


for tc in range(int(input())):
	(n, k) = map(int, input().split())
	h = list(map(int, input().split()))
	(dif, steps, base) = (0, 0, 0)
	for i in range(n):
		dif = h[i] - base
		if dif > k:
			steps += dif // k
			if dif % k == 0:
				steps -= 1
		base = h[i]
	print(steps)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	s = list(map(int, input().split()))
	curr = 0
	count = 0
	for i in range(n):
		count += (s[i] - curr - 1) // k
		curr = s[i]
	print(count)


from math import ceil
for t in range(int(input())):
	(n, k) = map(int, input().split())
	h = [0] + list(map(int, input().split()))
	c = 0
	for i in range(1, n + 1):
		if h[i] - h[i - 1] > k:
			c += ceil((h[i] - h[i - 1]) / k) - 1
	print(c)


t = int(input())
for i in range(t):
	(n, k) = list(map(int, input().split(' ')))
	arr = list(map(int, input().split(' ')))
	arr.insert(0, 0)
	count = 0
	p = 0
	q = 0
	for i in range(len(arr) - 1):
		if arr[i + 1] - arr[i] <= k:
			pass
		elif arr[i + 1] - arr[i] > k:
			p = arr[i + 1]
			q = arr[i]
			while p - q > k:
				q = q + k
				count += 1
	print(count)


t = int(input())
while t != 0:
	(n, k) = map(int, input().split())
	h = list(map(int, input().split()))[:n]
	ans = 0
	prev = 0
	for i in range(n):
		diff = h[i] - prev
		if diff > k:
			if diff % k == 0:
				ans += diff // k - 1
			else:
				ans += diff // k
		prev = h[i]
	print(ans)
	t -= 1


t = int(input())
while t != 0:
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	c = 0
	p = 0
	for j in range(n):
		if l[j] - p > k:
			c += (l[j] - p) // k
			if (l[j] - p) % k == 0:
				c -= 1
		p = l[j]
	print(c)
	t -= 1


t = int(input())
for i in range(t):
	x = input().split()
	n = int(x[0])
	k = int(x[1])
	heights = [int(h) for h in input().split()]
	h_f = 0
	steps = 0
	for j in range(n):
		if heights[j] - h_f > k:
			steps = steps + (heights[j] - h_f - 1) // k
		h_f = heights[j]
	print(steps)


for b in range(int(input())):
	(N, K) = map(int, input().split())
	stairs = list(map(int, input().split()))
	ans = 0
	lower = 0
	for i in range(N):
		diff = stairs[i] - lower
		if diff > K:
			if diff % K == 0:
				ans += diff // K - 1
			else:
				ans += diff // K
		lower = stairs[i]
	print(ans)


for i in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	d = 0
	if l[0] - 1 > k:
		d += (l[0] - 1) // k
	for i in range(n - 1):
		if l[i + 1] - l[i] > k:
			d += (l[i + 1] - l[i] - 1) // k
	print(d)


for i in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	c = 0
	if a[0] - 1 > k:
		c += (a[0] - 1) // k
	for i in range(n - 1):
		if a[i + 1] - a[i] > k:
			c += (a[i + 1] - a[i] - 1) // k
	print(c)


for t in range(int(input())):
	(N, K) = [int(x) for x in input().split()]
	H = [0] + [int(x) for x in input().split()]
	i = 0
	count = 0
	while i < N:
		if H[i + 1] - H[i] > K:
			count += int((H[i + 1] - H[i] - 1) / K)
		i += 1
	print(count)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	h = list(map(int, input().split()))
	h.insert(0, 0)
	cnt = 0
	for i in range(n):
		if h[i + 1] - h[i] > k:
			cnt += (h[i + 1] - h[i] - 1) // k
	print(cnt)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	(s, cnt) = (0, 0)
	l = list(map(int, input().split()))
	for i in range(n):
		if l[i] - s > k:
			if (l[i] - s) % k == 0:
				cnt = cnt - 1 + (l[i] - s) // k
			else:
				cnt = cnt + (l[i] - s) // k
		s = l[i]
	print(cnt)


t = int(input())
for t in range(t):
	(n, k) = [int(i) for i in input().split()]
	harr = [int(i) for i in input().split()]
	count = 0
	if harr[0] > k:
		count += harr[0] // k
		if harr[0] % k == 0:
			count -= 1
	for i in range(n - 1):
		d = harr[i + 1] - harr[i]
		if d > k:
			count += d // k
			if d % k == 0:
				count -= 1
	print(count)


t = int(input())
for i in range(t):
	current = 0
	count = 0
	(n, k) = [int(x) for x in input().split()]
	h = [int(y) for y in input().split()]
	for j in range(100000000):
		if current == h[-1]:
			break
		for aa in range(100000000):
			if abs(current - h[j]) <= k:
				current = h[j]
				break
			else:
				current += k
				count += 1
	print(count)


t = input()
for c in range(0, int(t)):
	a = input().split()
	n = int(a[0])
	k = int(a[1])
	p = 0
	s = 0
	for x in input().split():
		b = int(x) - p
		if b % k == 0:
			s += b / k - 1
		else:
			s += int(b / k)
		p = int(x)
	print(int(s))


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	heights = list(map(int, input().split()))
	length = len(heights)
	prev = 0
	noOfSteps = 0
	for i in range(length):
		difference = heights[i] - prev
		if difference % k == 0:
			noOfSteps += difference // k - 1
		else:
			noOfSteps += difference // k
		prev = heights[i]
	print(noOfSteps)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	h = list(map(int, input().split()))
	(diff, steps, base) = (0, 0, 0)
	for i in range(n):
		diff = h[i] - base
		if diff > k:
			steps += diff // k
			if diff % k == 0:
				steps -= 1
		base = h[i]
	print(steps)


t = int(input())
for i in range(0, t):
	(n, k) = map(int, input().split(' '))
	arr = list(map(int, input().split(' ')))
	steps = 0
	if arr[0] > k:
		if arr[0] % k == 0:
			steps += arr[0] // k - 1
		else:
			steps += arr[0] // k
	for i in range(1, n):
		diff = arr[i] - arr[i - 1]
		if diff > k:
			if diff % k == 0:
				steps += diff // k - 1
			else:
				steps += diff // k
	print(steps)


testcase = int(input())
for i in range(testcase):
	(n, k) = map(int, input().split())
	lst = list(map(int, input().split()))
	steps = 0
	prev = 0
	for nn in range(n):
		if lst[nn] - prev > k:
			steps += (lst[nn] - prev) // k
			if (lst[nn] - prev) % k == 0:
				steps -= 1
		prev = lst[nn]
	print(steps)


for i in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	l.sort()
	count = 0
	l.insert(0, 0)
	for i in range(len(l) - 1):
		if l[i + 1] - l[i] > k:
			if (l[i + 1] - l[i]) % k == 0:
				count += int((l[i + 1] - l[i]) / k) - 1
			else:
				count += int((l[i + 1] - l[i]) / k)
	print(count)


for _ in range(int(input())):
	(M, L) = map(int, input().split())
	g = list(map(int, input().split()))
	g.insert(0, 0)
	b = 0
	for i in range(1, M + 1):
		b += (g[i] - g[i - 1] - 1) // L
	print(b)


for _ in range(int(input())):
	(a, b) = map(int, input().split())
	l = [0]
	l.extend(list(map(int, input().split())))
	s = 0
	for i in range(1, a + 1):
		k = l[i] - l[i - 1]
		if b < k:
			if k % b == 0:
				s += k // b - 1
			else:
				s += k // b
	print(s)


try:
	for _ in range(int(input())):
		(n, k) = map(int, input().split())
		h = [int(x) for x in input().split()]
		(hf, c) = (0, 0)
		for i in h:
			if i - hf > k:
				c += (i - hf - 1) // k
			hf = i
		print(c)
except EOFError as e:
	pass


from sys import stdin, stdout
ans = []
for _ in range(int(stdin.readline())):
	(n, k) = map(int, stdin.readline().split())
	s_h = list(map(int, stdin.readline().split()))
	num = (s_h[0] - 1) // k
	for i in range(1, n):
		num += (s_h[i] - s_h[i - 1] - 1) // k
	ans.append(str(num))
stdout.write('\n'.join(ans))


from math import ceil
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	ans = 0
	a = [int(x) for x in input().split()]
	a = [0] + a
	for i in range(n):
		ans += ceil((a[i + 1] - a[i]) / k) - 1
	print(ans)


for i in range(int(input())):
	(a, b) = list(map(int, input().split()))
	y = list(map(int, input().split()))
	s = 0
	if y[0] > b:
		s += y[0] // b
		if y[0] % b == 0:
			s -= 1
	for j in range(1, a):
		diff = y[j] - y[j - 1]
		s += diff // b
		if diff % b == 0:
			s -= 1
	print(s)


for _ in range(int(input())):
	(N, K) = map(int, input().split())
	H = list(map(int, input().split()))
	H = [0] + H
	ans = 0
	for i in range(N):
		ans += (H[i + 1] - H[i] - 1) // K
	print(ans)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	h = list(map(int, input().split()))
	c = 0
	r = 0
	for i in range(n):
		if h[i] - r > k:
			c = c + (h[i] - r) // k
			if (h[i] - r) % k == 0:
				c -= 1
		r = h[i]
	print(c)


import math
tests = int(input())
for i in range(tests):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	ans = 0
	if arr[0] > k:
		ans += math.ceil((arr[0] - k) / k)
	for j in range(n):
		diff = arr[j] - arr[j - 1]
		if diff > k:
			ans += math.ceil((diff - k) / k)
	print(ans)


t = int(input())
for ni in range(t):
	(n, k) = map(int, input().split())
	h = [int(i) for i in input().split()]
	step = (h[0] - 1) // k
	for i in range(1, n):
		if h[i] - h[i - 1] > k:
			step = step + (h[i] - h[i - 1] - 1) // k
	print(step)


from math import *
t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	c = 0
	if l[0] > k and l[0] % k == 0:
		c = c + (l[0] // k - 1)
	elif l[0] > k and l[0] % k != 0:
		c = c + floor(l[0] / k)
	for i in range(n - 1):
		if l[i + 1] - l[i] <= k:
			continue
		elif l[i + 1] - l[i] > k and (l[i + 1] - l[i]) % k != 0:
			c = c + floor((l[i + 1] - l[i]) / k)
		else:
			c = c + (l[i + 1] - l[i]) // k - 1
	print(c)


for i in range(int(input())):
	(N, K) = map(int, input().split())
	H = []
	H = [int(x) for x in input().split()]
	highest = 0
	count = 0
	for k in H:
		if k - highest > K:
			count = count + (k - highest - 1) // K
		highest = k
	print(count)


for _ in range(int(input())):
	(N, K) = (int(i) for i in input().strip().split())
	stair_arr = [0]
	stair_arr.extend([int(i) for i in input().strip().split()])
	add_cnt = 0
	for i in range(1, N + 1):
		height_diff = stair_arr[i] - stair_arr[i - 1]
		if height_diff > K:
			add_cnt += height_diff // K
			if height_diff % K == 0:
				add_cnt -= 1
	print(add_cnt)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	h = list(map(int, input().split()))
	prev = 0
	c = 0
	for i in range(len(h)):
		diff = h[i] - prev
		if diff % k == 0:
			c += diff // k - 1
		else:
			c += diff // k
		prev = h[i]
	print(c)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = [int(i) for i in input().split()]
	i = 0
	c = 0
	if a[0] > k:
		if a[0] % k == 0:
			c += a[0] // k - 1
		else:
			c += a[0] // k
	while i < n - 1:
		z = a[i + 1] - a[i]
		if z % k == 0:
			c += z // k - 1
		else:
			c += z // k
		i += 1
	print(c)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	s = 0
	c = 0
	for j in l:
		if j - s > k:
			c += (j - s - 1) // k
		s = j
	print(c)


t = int(input())
while t:
	t -= 1
	(n, k) = map(int, input().split())
	l = [int(i) for i in input().split()]
	l.insert(0, 0)
	c = 0
	for i in range(1, n + 1):
		if l[i] - l[i - 1] > k:
			c += (l[i] - l[i - 1] - 1) // k
	print(c)


for i in range(int(input())):
	(n, k) = map(int, input().split())
	x = list(map(int, input().split()))
	y = 0
	if x[0] - 1 > k:
		y += (x[0] - 1) // k
	for i in range(n - 1):
		if x[i + 1] - x[i] > k:
			y += (x[i + 1] - x[i] - 1) // k
	print(y)


try:
	T = int(input())
	for i in range(T):
		(N, K) = map(int, input().split())
		H = list(map(int, input().split()))
		top = 0
		count = 0
		for j in H:
			if j - top > K:
				count = count + (j - top - 1) // K
			top = j
		print(count)
except EOFError as e:
	pass


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = [int(i) for i in input().split()]
	c = 0
	p = 0
	for i in range(n):
		if l[i] - p > k:
			c += (l[i] - p) // k
			if (l[i] - p) % k == 0:
				c -= 1
		p = l[i]
	print(c)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = [0] + list(map(int, input().split()))
	print(sum([(a[i + 1] - a[i] - 1) // k for i in range(n)]))