A spider present at the bottom of the well of height H, needs to get out of it. The walls of the well are very slippery. In each step, it climbs U metres and slips down D metres. If in the last step, the spider gets out of the well by climbing U metres, it does not slip back. Find the number of steps the spider takes.
Example 1:
Input: 
H = 200, U = 50, D = 1
Output: 5
Explaination: 
First Step: 50 -1 = 49 
Second Step: 49 + 50 - 1 = 98 
Third Step: 98 + 50 - 1 = 147 
Fouth Step: 147 + 50 - 1 = 196
Fifth Step: Reach beyond H.
Example 2:
Input: 
H = 100, U = 5, D = 3
Output: 49
Explanation:
A single step covers (U-D=2) in each step. 
You can cover 96 in 48 steps. In the 49th 
step increment by 5 and don't decrement by 3.
Example 3:
Input:
H = 10, U = 4, D = 1
Output: 4
Explaination:
First Step: 4 - 1 = 3
Second Step: 3 + 4 - 1 = 6 
Third Step: 6 + 4 - 1 = 9 
Fourth Step: 9+4 = 13 > 10
 
Your Task:
You do not need to read input or print anything. Your task is to complete the function minStep() which takes H, U and D as input parameters and returns the steps required to go beyond H.
Expected Time Complexity: O(1)
Expected Auxiliary Space: O(1)
Constraints:
50 ≤ H ≤ 1000
1 ≤ D < U ≤ 100

Source: geeksforgeeks | Difficulty: EASY
Tags: Mathematics

Greedy algorithms

Starter code: #User function Template for python3



class Solution:

    def minStep(self, H, U, D):

        # code here

Solutions:
import math

class Solution:

	def minStep(self, H, U, D):
		a = U - D
		b = H - D
		steps = b // a
		if steps * a + U >= H:
			return steps + 1
		else:
			return ('The total minimum steps to climb is', steps)


import math

class Solution:

	def minStep(self, H, U, D):
		return math.ceil((H - U + 1) / (U - D)) + 1


class Solution:

	def minStep(self, h, u, d):
		r = 0
		y = 0
		while y < h:
			r += 1
			if y + u > h:
				d = 0
			y += u - d
		return r


class Solution:

	def minStep(self, H, U, D):
		if H < U:
			return 1
		return 1 + self.minStep(H - (U - D), U, D)


class Solution:

	def minStep(self, H, U, D):
		count = 0
		clm = 0
		while clm < H:
			clm = clm + U
			count += 1
			if clm > H:
				break
			else:
				clm -= D
		return count


class Solution:

	def minStep(self, H, U, D):
		return int((H - D) / (U - D) + 1)


class Solution:

	def minStep(self, H, U, D):
		hey = 0
		count = 0
		while hey < H:
			if hey + U > H:
				return count + 1
			hey += U - D
			count += 1
		return count


class Solution:

	def minStep(self, H, U, D):
		x = U - D
		r = 0
		c = 0
		while r <= H - U:
			r += x
			c += 1
		return c + 1


class Solution:

	def minStep(self, H, U, D):
		ans = (H - D) // (U - D)
		return ans + 1


class Solution:

	def minStep(self, H, U, D):

		def f(n):
			if n > H:
				return 0
			return 1 + f(n + U - D)
		return 1 + f(U)


class Solution:

	def minStep(self, h, u, d):
		c = 0
		s = 0
		while s < h:
			s += u
			c = c + 1
			if s > h:
				break
			else:
				s -= d
		return c


class Solution:

	def minStep(self, H, U, D):
		k = H - U
		U = U - D
		if k <= 0:
			return 1
		return k // U + 2


class Solution:

	def minStep(self, H, U, D):
		if H > U:
			j = U - D
			c = 1
			while j < H:
				j = j + U
				c = c + 1
				if j > H:
					break
				else:
					j = j - D
			return c
		elif (U < D or U >= D) and H <= U:
			return 1
		else:
			return 2


class Solution:

	def minStep(self, H, U, D):
		reach = 0
		steps = 0
		while reach <= H:
			reach += U
			steps += 1
			if reach > H:
				break
			else:
				reach -= D
		return steps


class Solution:

	def minStep(self, H, U, D):
		a = 0
		s = 0
		if H <= U:
			return 1
		while H >= U:
			s += U
			a += 1
			if H < s:
				return a
			s = s - D


class Solution:

	def minStep(self, H, U, D):
		temp = 0
		cnt = 0
		while temp < H:
			temp += U
			if temp > H:
				return cnt + 1
			temp -= D
			cnt += 1
		return cnt


class Solution:

	def minStep(self, H, U, D):
		count = 1
		count += (H - D) // (U - D)
		return count


class Solution:

	def minStep(self, H, U, D):
		position = 0
		count = 0
		while True:
			position += U
			count += 1
			if position > H:
				return count
			position -= D


class Solution:

	def minStep(self, H, U, D):
		num = H - U
		s = U - D
		c = 1
		sm = 0
		while sm <= num:
			sm = sm + s
			c += 1
		return c


class Solution:

	def minStep(self, H, U, D):
		st = U - D
		c = 1
		ht = U
		while ht <= H:
			ht += st
			c += 1
		return c


class Solution:

	def minStep(self, H, U, D):
		c = (H - U) // (U - D)
		return c + 2


class Solution:

	def minStep(self, H, U, D):
		sh = H - D
		a = sh // (U - D)
		if a * (U - D) + U >= H:
			return a + 1


class Solution:

	def minStep(self, H, U, D):
		C = 0
		if H < U:
			return 1
		else:
			R = (H - U) // (U - D)
			C = R + 2
		return C


class Solution:

	def minStep(self, H, U, D):
		cnt = 0
		Steps = 0
		while Steps < H:
			Steps = Steps + U
			cnt += 1
			if Steps > H:
				break
			else:
				Steps -= D
		return cnt


class Solution:

	def minStep(self, H, U, D):
		step = 0
		total = 0
		while total < H + 1:
			total += U
			step += 1
			if total < H + 1:
				total -= D
		return step


class Solution:

	def minStep(self, H, U, D):
		step = U - D
		H = H + 1 - U
		ans = 1
		if H % step == 0:
			ans += H // step
		else:
			ans += H // step + 1
		return ans


class Solution:

	def minStep(self, H, U, D):
		res = (H - D) // (U - D)
		return res + 1


class Solution:

	def minStep(self, H, U, D):
		step = (H - D) // (U - D)
		ans = step + 1
		return ans
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(H, U, D) = [int(x) for x in input().split()]
		ob = Solution()
		print(ob.minStep(H, U, D))


class Solution:

	def minStep(self, H, U, D):
		ht = c = 0
		while ht <= H - U:
			ht += U - D
			c += 1
		return c + 1
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(H, U, D) = [int(x) for x in input().split()]
		ob = Solution()
		print(ob.minStep(H, U, D))


class Solution:

	def minStep(self, H, U, D):
		climbed = 0
		count = 0
		while True:
			count += 1
			climbed += U
			if climbed > H:
				return count
			climbed -= D
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(H, U, D) = [int(x) for x in input().split()]
		ob = Solution()
		print(ob.minStep(H, U, D))


import math

class Solution:

	def minStep(self, H, U, D):
		H = H - U + 1
		e = math.ceil(H / (U - D))
		return e + 1
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(H, U, D) = [int(x) for x in input().split()]
		ob = Solution()
		print(ob.minStep(H, U, D))


class Solution:

	def minStep(self, H, U, D):
		cnt = 1
		x = U
		while x <= H:
			x = x + U - D
			cnt += 1
		return cnt


class Solution:

	def minStep(self, H, U, D):
		if U > H:
			return 1
		if (H - U) // (U - D) <= H - U:
			return (H - U) // (U - D) + 2
		else:
			return (H - U) // (U - D) + 1


class Solution:

	def minStep(self, H, U, D):
		x = (H - D) // (U - D)
		return x + 1


class Solution:

	def minStep(self, H, U, D):
		sum = U
		count = 1
		while sum <= H:
			sum = sum - D
			count += 1
			sum = sum + U
		return count


class Solution:

	def minStep(self, H, U, D):
		steps = (H - D) // (U - D)
		steps += 1
		return steps


class Solution:

	def minStep(self, H, U, D):
		c = 0
		d = 0
		diff = U - D
		while c + U <= H:
			d += 1
			c += diff
		return d + 1


class Solution:

	def minStep(self, H, U, D):
		last = H + 1 - U
		if last % (U - D) == 0:
			n = last // (U - D)
		else:
			n = last // (U - D) + 1
		return n + 1


class Solution:

	def minStep(self, H, U, D):
		h = 0
		cnt = 0
		diff = U - D
		while h + U <= H:
			cnt += 1
			h += diff
		return cnt + 1


class Solution:

	def minStep(self, H, U, D):
		cur = 0
		ans = 0
		while True:
			ans += 1
			cur += U
			if cur > H:
				return ans
			cur -= D
		return ans


class Solution:

	def minStep(self, H, U, D):
		k = 0
		while H > 0:
			H = H - U
			k = k + 1
			if H < 0:
				break
			H = H + D
		return k


class Solution:

	def minStep(self, H, U, D):
		z = 0
		c = 0
		while z < H:
			z += U
			if z > H:
				c += 1
				break
			else:
				z = z - D
				c += 1
		return c


class Solution:

	def minStep(self, H, U, D):
		step = 1
		climb = U
		diff = U - D
		step += (H - U + diff) // diff
		return step


class Solution:

	def minStep(self, H, U, D):
		sh = th = c = 0
		while th < H:
			sh = U - D
			if th + U > H:
				th += U
			else:
				th = th + sh
			c += 1
		return c


class Solution:

	def minStep(self, H, U, D):
		diff = U - D
		total = 0
		nu = 0
		while H > total:
			nu += 1
			if total + U > H:
				break
			else:
				total += diff
		return nu


class Solution:

	def minStep(self, H, U, D):
		step_count = 0
		step_val = 0
		while step_val < H:
			step_val += U
			if step_val > H:
				break
			else:
				step_val -= D
				step_count += 1
		return step_count + 1


class Solution:

	def minStep(self, H, U, D):
		c = 1
		c += (H - D) // (U - D)
		return c


class Solution:

	def minStep(self, H, U, D):
		t = U - D
		m = (H - D) // t
		return m + 1


import math

class Solution:

	def minStep(self, H, U, D):
		if (H - U) % (U - D) == 0:
			return (H - U) // (U - D) + 2
		else:
			return math.ceil((H - U) / (U - D)) + 1