You are given K eggs, and you have access to a building with N floors from 1 to N. 
Each egg is identical in function, and if an egg breaks, you cannot drop it again.
You know that there exists a floor F with 0 <= F <= N such that any egg dropped at a floor higher than F will break, and any egg dropped at or below floor F will not break.
Each move, you may take an egg (if you have an unbroken one) and drop it from any floor X (with 1 <= X <= N). 
Your goal is to know with certainty what the value of F is.
What is the minimum number of moves that you need to know with certainty what F is, regardless of the initial value of F?
 



Example 1:
Input: K = 1, N = 2
Output: 2
Explanation: 
Drop the egg from floor 1.  If it breaks, we know with certainty that F = 0.
Otherwise, drop the egg from floor 2.  If it breaks, we know with certainty that F = 1.
If it didn't break, then we know with certainty F = 2.
Hence, we needed 2 moves in the worst case to know what F is with certainty.


Example 2:
Input: K = 2, N = 6
Output: 3


Example 3:
Input: K = 3, N = 14
Output: 4

 
Note:

1 <= K <= 100
1 <= N <= 10000

Source: leetcode | Difficulty: MEDIUM
Tags: Dynamic programming

Sorting

Mathematics

Starter code: class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        

Solutions:
class Solution:

	def superEggDrop(self, K: int, N: int) -> int:

		def f(t):
			a = 0
			r = 1
			for i in range(1, K + 1):
				r *= t - i + 1
				r //= i
				a += r
				if a >= N:
					break
			return a
		(l, h) = (1, N)
		while l < h:
			m = (l + h) // 2
			if f(m) < N:
				l = m + 1
			else:
				h = m
		return l


class Solution:

	def superEggDrop(self, K: int, N: int) -> int:

		def aux(t, k):
			ret = 0
			r = 1
			for i in range(1, K + 1):
				r *= t - i + 1
				r //= i
				ret += r
				if ret >= N:
					break
			return ret
		(l, r) = (1, N)
		while l < r:
			m = (l + r) // 2
			if aux(m, K) < N:
				l = m + 1
			else:
				r = m
		return l


class Solution:

	def superEggDrop(self, K: int, N: int) -> int:
		M = 300
		dp = [[0 for j in range(K + 1)] for i in range(M + 1)]
		for i in range(1, M + 1):
			for j in range(1, K + 1):
				dp[i][j] = 1 + dp[i - 1][j] + dp[i - 1][j - 1]
				if dp[i][j] >= N:
					return i


class Solution:

	def superEggDrop(self, K: int, N: int) -> int:
		dp = [[0] * (N + 1) for _ in range(K + 1)]
		for k in range(1, K + 1):
			for n in range(1, N + 1):
				if k == 1:
					dp[k][n] = n
				else:
					dp[k][n] = 1 + dp[k - 1][n - 1] + dp[k][n - 1]
		(top, bott) = (0, N)
		while top < bott:
			mid = (top + bott) // 2
			if dp[K][mid] < N:
				top = mid + 1
			else:
				bott = mid
		return bott


from functools import lru_cache

class Solution:

	def superEggDrop(self, K: int, N: int) -> int:

		@lru_cache(None)
		def dp(k, n):
			if k == 0:
				return 0
			if k == 1:
				return n
			if n <= 1:
				return n
			if k > math.log(n, 2):
				return 1 + int(math.log(n, 2))
			(l, r) = (1, n + 1)
			while l < r:
				m = l + (r - l) // 2
				if dp(k - 1, m - 1) >= dp(k, n - m):
					r = m
				else:
					l = m + 1
			return 1 + max(dp(k - 1, l - 1), dp(k, n - l))
		return dp(K, N)


class Solution:

	def superEggDrop(self, K: int, N: int) -> int:
		dp = list(range(N + 1))
		for i in range(2, K + 1):
			k = 1
			temp = [0] + [N + 1] * N
			for j in range(1, N + 1):
				while k < j + 1 and temp[j - k] > dp[k - 1]:
					k += 1
				temp[j] = 1 + dp[k - 1]
			dp = temp[:]
		return dp[-1]


class Solution:

	def superEggDrop(self, K: int, N: int) -> int:
		self.memo = {}
		return self.cal_eggs(K, N)

	def find_that_floor(self, K, N):
		(left, right) = (1, N)
		while left <= right:
			mid = (left + right) // 2
			r1 = 1 + self.cal_eggs(K - 1, mid - 1)
			r2 = 1 + self.cal_eggs(K, N - mid)
			if r1 == r2:
				right = mid
				break
			elif r1 < r2:
				left = mid + 1
			else:
				right = mid - 1
		return right

	def cal_eggs(self, K, N):
		if N == 0:
			return 0
		if K == 1:
			return N
		if (K, N) in self.memo:
			pass
		else:
			r = 2 ** 32 - 1
			now_floor = self.find_that_floor(K, N)
			for floor in range(now_floor, min(now_floor + 2, N + 1)):
				r1 = 1 + self.cal_eggs(K - 1, floor - 1)
				r2 = 1 + self.cal_eggs(K, N - floor)
				r = min(r, max(r1, r2))
			self.memo[K, N] = r
		return self.memo[K, N]


class Solution:

	def superEggDrop(self, K: int, N: int) -> int:
		max_floors = [[0 for _ in range(N + 1)] for _ in range(K + 1)]
		for k in range(1, K + 1):
			for t in range(1, N + 1):
				max_floors[k][t] = 1 + max_floors[k - 1][t - 1] + max_floors[k][t - 1]
		for t in range(N):
			if max_floors[K][t] >= N:
				return t
		return N


class Solution:

	def f(self, pivot: int, eggs: int, floors: int) -> int:
		(ans, r) = (0, 1)
		for idx in range(1, eggs + 1):
			r *= pivot - idx + 1
			r //= idx
			ans += r
			if ans >= floors:
				break
		return ans

	def superEggDrop(self, eggs: int, floors: int) -> int:
		(lo, hi) = (1, floors)
		while lo < hi:
			mi = (lo + hi) // 2
			if self.f(mi, eggs, floors) < floors:
				lo = mi + 1
			else:
				hi = mi
		return lo


class Solution:

	def superEggDrop(self, K: int, N: int) -> int:
		from functools import lru_cache

		@lru_cache(maxsize=None)
		def dp(i, j):
			if j == 0:
				return 0
			if i == 1:
				return j
			if j == 1:
				return 1
			(lo, hi) = (1, j)
			while lo < hi:
				k = lo + (hi - lo) // 2
				if dp(i - 1, k - 1) < dp(i, j - k):
					lo = k + 1
				else:
					hi = k
			return 1 + dp(i - 1, lo - 1)
		return dp(K, N)


from functools import lru_cache

class Solution:

	def superEggDrop(self, K: int, N: int) -> int:

		@lru_cache(None)
		def dp(k: int, n: int) -> int:
			if k <= 0:
				return 1 << 31
			if k == 1:
				return n
			if n <= 0:
				return 0
			if n <= 1:
				return n
			(left, right) = (1, n)
			while left <= right:
				mid = (left + right) // 2
				if dp(k - 1, mid - 1) >= dp(k, n - mid):
					right = mid - 1
				else:
					left = mid + 1
			return 1 + dp(k - 1, left - 1)
		return dp(K, N)


class Solution:

	def binary_search(self, A, k, n):
		lo = 0
		hi = n
		mid = (lo + hi) // 2
		while lo < hi:
			if A[k - 1][mid - 1] == A[k][n - mid]:
				return mid
			if A[k - 1][mid - 1] > A[k][n - mid]:
				hi = mid
			else:
				lo = mid + 1
			mid = (lo + hi) // 2
		return lo

	def superEggDrop(self, K: int, N: int) -> int:
		if N == 1:
			return 1
		A = [[0 for n in range(N + 1)] for k in range(K + 1)]
		for n in range(N + 1):
			A[1][n] = n
		for k in range(K + 1):
			A[k][1] = 1
			A[k][2] = 2
		for k in range(2, K + 1):
			low = 1
			for n in range(3, N + 1):
				if A[k - 1][low] < A[k][n - low - 1]:
					low += 1
				A[k][n] = 1 + A[k - 1][low]
		return A[-1][-1]


class Solution:

	def superEggDrop(self, K: int, N: int) -> int:

		@lru_cache(None)
		def dp(k, n):
			if n == 0:
				ans = 0
			elif k == 1:
				ans = n
			else:
				(lo, hi) = (1, n)
				while lo < hi:
					x = (lo + hi) // 2
					t1 = dp(k - 1, x - 1)
					t2 = dp(k, n - x)
					if t1 < t2:
						lo = x + 1
					else:
						hi = x
				ans = 1 + max(dp(k - 1, lo - 1), dp(k, n - lo))
			return ans
		return dp(K, N)


class Solution:

	def superEggDrop(self, K: int, N: int) -> int:
		memo = {}

		def dp(k, n):
			if (k, n) not in memo:
				if n == 0:
					ans = 0
				elif k == 1:
					ans = n
				else:
					(lo, hi) = (1, n)
					while lo + 1 < hi:
						x = (lo + hi) // 2
						t1 = dp(k - 1, x - 1)
						t2 = dp(k, n - x)
						if t1 < t2:
							lo = x
						elif t1 > t2:
							hi = x
						else:
							lo = hi = x
					ans = 1 + min((max(dp(k - 1, x - 1), dp(k, n - x)) for x in (lo, hi)))
				memo[k, n] = ans
			return memo[k, n]
		return dp(K, N)


class Solution:

	def superEggDrop(self, K: int, N: int) -> int:
		dp = [[i for i in range(N + 1)]]
		for i in range(K - 1):
			dp.append([0] * (N + 1))
		for i in range(1, K):
			k = 1
			for j in range(1, N + 1):
				while k < j + 1 and dp[i][j - k] > dp[i - 1][k - 1]:
					k += 1
				dp[i][j] = 1 + dp[i - 1][k - 1]
		return dp[-1][-1]


class Solution:

	def superEggDrop(self, K: int, N: int) -> int:
		mem = [[None for _ in range(N)] for _ in range(K - 1)]

		def dp(k, n, mem):
			if n <= 1 or k == 1:
				return n
			if mem[k - 2][n - 1] is None:
				(l, r) = (1, n)
				while l + 1 < r:
					i = (l + r) // 2
					if dp(k - 1, i - 1, mem) < dp(k, n - i, mem):
						l = i
					elif dp(k - 1, i - 1, mem) > dp(k, n - i, mem):
						r = i
					else:
						l = r = i
				mem[k - 2][n - 1] = min(max(dp(k - 1, l - 1, mem), dp(k, n - l, mem)), max(dp(k - 1, r - 1, mem), dp(k, n - r, mem))) + 1
			return mem[k - 2][n - 1]
		return dp(K, N, mem)


class Solution(object):

	def superEggDrop(self, K, N):
		dp = [[float('inf')] * (N + 1) for _ in range(K + 1)]
		for i in range(1, K + 1):
			dp[i][0] = 0
			dp[i][1] = 1
		for j in range(1, N + 1):
			dp[1][j] = j
		for i in range(2, K + 1):
			k = 1
			for j in range(2, N + 1):
				while k < j + 1 and dp[i][j - k] > dp[i - 1][k - 1]:
					k += 1
				dp[i][j] = 1 + dp[i - 1][k - 1]
		return dp[K][N]


class Solution:

	def superEggDrop(self, K: int, N: int) -> int:
		dp = [[float('Inf')] * (N + 1) for _ in range(K + 1)]
		for i in range(1, K + 1):
			(dp[i][0], dp[i][1]) = (0, 1)
		for j in range(1, N + 1):
			dp[1][j] = j
		for i in range(2, K + 1):
			k = 1
			for j in range(2, N + 1):
				while k < j + 1 and dp[i][j - k] > dp[i - 1][k - 1]:
					k += 1
				dp[i][j] = 1 + dp[i - 1][k - 1]
		return dp[K][N]


class Solution:

	def superEggDrop(self, K: int, N: int) -> int:
		res = [[0] * (N + 1) for _ in range(K)]
		for i in range(N + 1):
			res[0][i] = i
		if K == 1:
			return N
		for k in range(1, K):
			j = 1
			for i in range(1, N + 1):
				while j < i + 1 and res[k - 1][j - 1] < res[k][i - j]:
					j += 1
				res[k][i] = 1 + res[k - 1][j - 1]
		return int(res[K - 1][N])


class Solution:

	def superEggDrop(self, K: int, N: int) -> int:
		dp = [[float('inf')] * (N + 1) for _ in range(K + 1)]
		for k in range(1, K + 1):
			dp[k][1] = 1
			dp[k][0] = 0
		for n in range(1, N + 1):
			dp[1][n] = n
		for k in range(2, K + 1):
			x = 1
			for n in range(2, N + 1):
				while x < n + 1 and dp[k][n - x] > dp[k - 1][x - 1]:
					x += 1
				dp[k][n] = 1 + dp[k - 1][x - 1]
		return dp[-1][-1]


class Solution:

	def superEggDrop(self, k: int, n: int) -> int:
		memo = {}

		def dp(k, n):
			if (k, n) not in memo:
				if n == 0:
					ans = 0
				elif k == 1:
					ans = n
				else:
					(l, r) = (1, n)
					while l + 1 < r:
						x = (l + r) // 2
						t1 = dp(k - 1, x - 1)
						t2 = dp(k, n - x)
						if t1 < t2:
							l = x
						elif t1 > t2:
							r = x
						else:
							l = r = x
					ans = 1 + min((max(dp(k - 1, x - 1), dp(k, n - x)) for x in (l, r)))
				memo[k, n] = ans
			return memo[k, n]
		return dp(k, n)


from functools import lru_cache

class Solution:

	def superEggDrop(self, K: int, N: int) -> int:

		@lru_cache(None)
		def dp(k, n):
			if k == 0:
				return 0
			if k == 1:
				return n
			if n <= 1:
				return n
			ans = sys.maxsize
			(l, r) = (1, n + 1)
			while l < r:
				m = l + (r - l) // 2
				if dp(k - 1, m - 1) >= dp(k, n - m):
					r = m
				else:
					l = m + 1
			ans = min(ans, 1 + max(dp(k - 1, l - 1), dp(k, n - l)))
			return ans
		return dp(K, N)


class Solution:

	def superEggDrop(self, K: int, N: int) -> int:
		if K == 1:
			return N
		Rp = [i for i in range(0, N + 1)]
		R = [0] * (N + 1)
		R[1] = 1
		k = 2
		while k <= K:
			l1 = 0
			for n in range(2, N + 1):
				if Rp[n - l1 - 1] >= R[n - 1]:
					R[n] = R[n - 1] + 1
				else:
					R[n] = R[n - 1]
				if R[n] > R[n - 1]:
					l1 = n - 1
			(Rp, R) = (R, Rp)
			k += 1
		return Rp[N]


class Solution:

	def superEggDrop(self, K: int, N: int) -> int:
		dp = [[0 for egg in range(K + 1)] for moves in range(305)]
		print(N)
		for move in range(1, 300):
			for eggs in range(1, K + 1):
				dp[move][eggs] = 1 + dp[move - 1][eggs - 1] + dp[move - 1][eggs]
				if dp[move][eggs] >= N:
					return move


class Solution:

	def superEggDrop(self, K: int, N: int) -> int:
		if N == 1:
			return 1
		eggSolutions = [[None for n in range(N + 1)] for k in range(K + 1)]
		for n in range(1, N + 1):
			eggSolutions[1][n] = n
		for k in range(1, K + 1):
			eggSolutions[k][1] = 1
			eggSolutions[k][2] = 2
		nextPVals = [i for i in range(N + 1)]
		for k in range(2, K + 1):
			pVals = nextPVals
			nextPVals = [None, None, 2]
			pIndex = 2
			for n in range(3, N + 1):
				p = pVals[pIndex]
				minDrops = 1 + max(eggSolutions[k - 1][p - 1], eggSolutions[k][n - p])
				eggSolutions[k][n] = minDrops
				if eggSolutions[k][n] > eggSolutions[k][n - 1]:
					pIndex += 1
					nextPVals.append(n)
		return eggSolutions[K][N]


class Solution:

	def superEggDrop(self, K: int, N: int) -> int:

		@lru_cache(None)
		def dp(k, n):
			if n == 0:
				return 0
			if k == 1:
				return n
			res = float('inf')
			lo = 1
			hi = n
			while lo <= hi:
				mid = (lo + hi) // 2
				broken = dp(k - 1, mid - 1)
				no_broken = dp(k, n - mid)
				if broken > no_broken:
					hi = mid - 1
					res = min(res, broken + 1)
				else:
					lo = mid + 1
					res = min(res, no_broken + 1)
			return res
		return dp(K, N)


class Solution:

	def superEggDrop(self, K: int, N: int) -> int:
		dp = [i for i in range(N + 1)]
		for j in range(1, K):
			prev = dp.copy()
			m = 1
			for i in range(2, N + 1):
				while m < i and dp[i - m] >= prev[m - 1] and (dp[i - m - 1] >= prev[m]):
					m += 1
				dp[i] = max(dp[i - m], prev[m - 1]) + 1
		return dp[N]


class Solution:

	def superEggDrop(self, K: int, N: int) -> int:
		dp = [[0] * (N + 1) for _ in range(K + 1)]
		for n in range(1, N + 1):
			dp[1][n] = n
		for k in range(2, K + 1):
			dp[k][1] = 1
		for k in range(2, K + 1):
			m = 1
			for n in range(2, N + 1):
				while m < n and dp[k - 1][m - 1] < dp[k][n - m]:
					m += 1
				dp[k][n] = max(dp[k - 1][m - 1], dp[k][n - m]) + 1
		return dp[-1][-1]


from functools import lru_cache

class Solution:

	def superEggDrop(self, K: int, N: int) -> int:
		return self.findMoves(K, N)

	@lru_cache(maxsize=None)
	def findMoves(self, K, N):
		if K == 1 or N <= 1:
			return N
		f = N
		(left, right) = (1, N)
		while left < right:
			mid = (left + right) // 2
			broken = self.findMoves(K - 1, mid - 1)
			intact = self.findMoves(K, N - mid)
			if broken > intact:
				right = mid
			else:
				left = mid + 1
		mid = left - 1
		return 1 + max(self.findMoves(K - 1, mid - 1), self.findMoves(K, N - mid))

	def bottomUp(self, K, N):
		dp = [[i for i in range(N + 1)] for _ in range(K + 1)]
		for i in range(2, K + 1):
			for j in range(1, N + 1):
				min_drops = N
				for k in range(1, j + 1):
					min_drops = min(min_drops, 1 + max(dp[i - 1][k - 1], dp[i][j - k]))
				dp[i][j] = min_drops
		return dp[K][N]


import numpy as np

class Solution:

	def superEggDrop(self, K: int, N: int) -> int:
		drops = 0
		floors = [0 for _ in range(K + 1)]
		while floors[K] < N:
			for eggs in range(K, 0, -1):
				floors[eggs] += 1 + floors[eggs - 1]
			drops += 1
		return drops


class Solution:

	def superEggDrop1(self, K: int, N: int) -> int:
		memo = [[2 ** 31 - 1] * (N + 1) for _ in range(K + 1)]

		def dp(k, n):
			if k == 0:
				return 0
			if k == 1:
				return n
			if n <= 1:
				return n
			if memo[k][n] < 2 ** 31 - 1:
				return memo[k][n]
			ans = memo[k][n]
			for i in range(1, n + 1):
				ans = min(ans, 1 + max(dp(k - 1, i - 1), dp(k, n - i)))
			memo[k][n] = ans
			return ans
		return dp(K, N)

	def superEggDrop(self, K: int, N: int) -> int:
		memo = [[2 ** 31 - 1] * (N + 1) for _ in range(K + 1)]

		def dp(k, n):
			if k == 0:
				return 0
			if k == 1:
				return n
			if n <= 1:
				return n
			if memo[k][n] < 2 ** 31 - 1:
				return memo[k][n]
			left = 1
			right = n + 1
			while left < right:
				mid = left + (right - left) // 2
				if dp(k - 1, mid - 1) >= dp(k, n - mid):
					right = mid
				else:
					left = mid + 1
			memo[k][n] = 1 + max(dp(k - 1, left - 1), dp(k, n - left))
			return memo[k][n]
		return dp(K, N)


from math import comb

class Solution:

	def superEggDrop(self, K: int, N: int) -> int:
		dp = {}
		for i in range(N + 1):
			dp[i, 0] = 0
		for k in range(1, K + 1):
			dp[1, k] = 1
		for k in range(1, K + 1):
			for n in range(2, N + 1):
				dp[n, k] = 1 + dp[n - 1, k] + dp[n - 1, k - 1]
		num = 1
		while dp[num, K] < N:
			num += 1
		return num


class Solution:

	def superEggDrop(self, eggs: int, floors: int) -> int:
		dp = [[-1 for _ in range(floors + 1)] for _ in range(eggs + 1)]

		def search(eggs, floors):
			if eggs <= 0:
				return 0
			elif eggs == 1:
				return floors
			elif floors <= 1:
				return floors
			elif dp[eggs][floors] != -1:
				return dp[eggs][floors]
			(l, r) = (1, floors + 1)
			while l < r:
				mid = l + (r - l) // 2
				broken = search(eggs - 1, mid - 1)
				intact = search(eggs, floors - mid)
				if broken < intact:
					l = mid + 1
				else:
					r = mid
			dp[eggs][floors] = 1 + search(eggs - 1, l - 1)
			return dp[eggs][floors]
		return search(eggs, floors)


class Solution:

	def superEggDrop(self, K: int, N: int) -> int:
		memo = [[-1] * (K + 1) for _ in range(N + 1)]

		@lru_cache(None)
		def drop(egg, floor):
			if egg == 1 or floor <= 1:
				return floor
			if memo[floor][egg] != -1:
				return memo[floor][egg]
			minAttempts = float('inf')
			l = 1
			h = floor
			while l <= h:
				mid = (l + h) // 2
				low = drop(egg - 1, mid - 1)
				high = drop(egg, floor - mid)
				attempts = 1 + max(low, high)
				if low < high:
					l = mid + 1
				else:
					h = mid - 1
				minAttempts = min(minAttempts, attempts)
			memo[floor][egg] = minAttempts
			return minAttempts
		return drop(K, N)


class Solution:

	def superEggDrop(self, K: int, N: int) -> int:
		memo = {}

		def DP(k, n):
			if (k, n) not in memo:
				if n == 0:
					res = 0
				elif k == 1:
					res = n
				else:
					(l, r) = (1, n)
					while l < r:
						mid = (l + r) // 2
						t1 = DP(k - 1, mid - 1)
						t2 = DP(k, n - mid)
						if t1 < t2:
							l = mid + 1
						else:
							r = mid
					res = 1 + max(DP(k - 1, l - 1), DP(k, n - l))
				memo[k, n] = res
			return memo[k, n]
		return DP(K, N)


class Solution:

	def superEggDrop1(self, K: int, N: int) -> int:
		memo = [[2 ** 31 - 1] * (N + 1) for _ in range(K + 1)]

		def dp(k, n):
			if k == 0:
				return 0
			if k == 1:
				return n
			if n <= 1:
				return n
			if memo[k][n] < 2 ** 31 - 1:
				return memo[k][n]
			ans = memo[k][n]
			for i in range(1, n + 1):
				ans = min(ans, 1 + max(dp(k - 1, i - 1), dp(k, n - i)))
			memo[k][n] = ans
			return ans
		return dp(K, N)

	def superEggDrop3(self, K: int, N: int) -> int:
		memo = [[2 ** 31 - 1] * (N + 1) for _ in range(K + 1)]

		def dp(k, n):
			if k == 0:
				return 0
			if k == 1:
				return n
			if n <= 1:
				return n
			if memo[k][n] < 2 ** 31 - 1:
				return memo[k][n]
			left = 1
			right = n + 1
			res = 2 ** 31 - 1
			while left < right:
				mid = left + (right - left) // 2
				broken = dp(k - 1, mid - 1)
				notbroken = dp(k, n - mid)
				if broken >= notbroken:
					right = mid
					res = min(res, broken + 1)
				else:
					left = mid + 1
					res = min(res, notbroken + 1)
			memo[k][n] = res
			return memo[k][n]
		return dp(K, N)

	def superEggDrop(self, K, N):
		amax = 2 ** 31 - 1
		memo = [[amax] * (N + 1) for _ in range(K + 1)]

		def dp(k, n):
			if k == 0:
				return 0
			if k == 1:
				return n
			if n <= 1:
				return n
			if memo[k][n] != amax:
				return memo[k][n]
			left = 1
			right = n + 1
			while left < right:
				mid = left + (right - left) // 2
				broken = dp(k - 1, mid - 1)
				notbroken = dp(k, n - mid)
				if broken >= notbroken:
					right = mid
				else:
					left = mid + 1
			ans = 1 + max(dp(k - 1, left - 1), dp(k, n - left))
			memo[k][n] = ans
			return ans
		return dp(K, N)

	def superEggDrop2(self, K: int, N: int) -> int:
		memo = [[2 ** 31 - 1] * (N + 1) for _ in range(K + 1)]

		def dp(k, n):
			if k == 0:
				return 0
			if k == 1:
				return n
			if n <= 1:
				return n
			if memo[k][n] < 2 ** 31 - 1:
				return memo[k][n]
			left = 1
			right = n + 1
			while left < right:
				mid = left + (right - left) // 2
				if dp(k - 1, mid - 1) >= dp(k, n - mid):
					right = mid
				else:
					left = mid + 1
			memo[k][n] = 1 + max(dp(k - 1, left - 1), dp(k, n - left))
			return memo[k][n]
		return dp(K, N)

	def superEggDrop4(self, K, N):

		def f(x):
			ans = 0
			r = 1
			for i in range(1, K + 1):
				r *= x - i + 1
				r //= i
				ans += r
				if ans >= N:
					break
			return ans
		(lo, hi) = (1, N)
		while lo < hi:
			mi = (lo + hi) // 2
			if f(mi) < N:
				lo = mi + 1
			else:
				hi = mi
		return lo


class Solution:

	def superEggDrop(self, K: int, N: int) -> int:
		dp = [[0] * (K + 1) for i in range(N + 1)]
		for m in range(1, N + 1):
			for k in range(1, K + 1):
				dp[m][k] = dp[m - 1][k - 1] + dp[m - 1][k] + 1
			if dp[m][K] >= N:
				return m
		return search(N, K)


class Solution:

	def superEggDrop(self, K: int, N: int) -> int:
		memo = dict()

		def dp(k, n):
			if k == 1:
				return n
			if n == 0:
				return 0
			if (k, n) in memo:
				return memo[k, n]
			res = float('inf')
			res = float('inf')
			(lo, hi) = (1, n)
			while lo <= hi:
				mid = lo + (hi - lo) // 2
				broken = dp(k - 1, mid - 1)
				not_broken = dp(k, n - mid)
				if not_broken > broken:
					lo = mid + 1
					res = min(res, not_broken + 1)
				else:
					hi = mid - 1
					res = min(res, broken + 1)
			memo[k, n] = res
			return res
		return dp(K, N)


class Solution:

	def superEggDrop(self, e: int, f: int) -> int:
		self.cache = [[-1] * (f + 1) for _ in range(e + 1)]
		return self.drop(e, f)

	def drop(self, e, f):
		if f == 0 or f == 1:
			return f
		if e == 1:
			return f
		if self.cache[e][f] != -1:
			return self.cache[e][f]
		ans = float('inf')
		l = 1
		h = f
		while l <= h:
			mid = (l + h) // 2
			low = 0
			high = 0
			if self.cache[e - 1][mid - 1] != -1:
				low = self.cache[e - 1][mid - 1]
			else:
				low = self.drop(e - 1, mid - 1)
			if self.cache[e][f - mid] != -1:
				high = self.cache[e][f - mid]
			else:
				high = self.drop(e, f - mid)
			if low < high:
				l = mid + 1
			else:
				h = mid - 1
			ans = min(max(low, high) + 1, ans)
		self.cache[e][f] = ans
		return ans


class Solution:

	def superEggDrop(self, K: int, N: int) -> int:
		memo = {}

		def dfs(k, n):
			if k == 1:
				return n
			if n <= 1:
				return n
			if (k, n) in memo:
				return memo[k, n]
			(l, r) = (0, n)
			while l < r:
				mid = l + (r - l) // 2
				left_cnt = dfs(k - 1, mid - 1)
				right_cnt = dfs(k, n - mid)
				if left_cnt < right_cnt:
					l = mid + 1
				else:
					r = mid
			memo[k, n] = 1 + max(dfs(k - 1, l - 1), dfs(k, n - l))
			return memo[k, n]
		return dfs(K, N)


class Solution:

	def superEggDrop(self, K: int, N: int) -> int:
		memo = dict()

		def dp(K, N):
			if K == 1:
				return N
			if N == 0:
				return 0
			if (K, N) in memo:
				return memo[K, N]
			(low, high) = (1, N + 1)
			while low < high:
				mid = (low + high) // 2
				broken = dp(K - 1, mid - 1)
				notBroken = dp(K, N - mid)
				if broken >= notBroken:
					high = mid
				else:
					low = mid + 1
			memo[K, N] = 1 + max(dp(K - 1, low - 1), dp(K, N - low))
			return memo[K, N]
		return dp(K, N)


class Solution:

	def superEggDrop(self, K: int, N: int) -> int:
		memo = {}

		def dp(k, n):
			if k <= 0:
				return 0
			if k == 1:
				return n
			if n <= 1:
				return n
			if (k, n) in memo:
				return memo[k, n]
			(l, r) = (1, n + 1)
			while l < r:
				mid = l + (r - l) // 2
				broken = dp(k - 1, mid - 1)
				unbroken = dp(k, n - mid)
				if broken >= unbroken:
					r = mid
				else:
					l = mid + 1
			memo[k, n] = 1 + dp(k - 1, l - 1)
			return memo[k, n]
		return dp(K, N)


class Solution(object):

	def superEggDrop(self, K, N):

		def dfs(i, j):
			if i == 1:
				return j
			if j == 0:
				return 0
			if j == 1:
				return 1
			if (i, j) in d:
				return d[i, j]
			(lo, hi) = (0, j)
			while lo < hi:
				mid = (lo + hi) // 2
				(left, right) = (dfs(i - 1, mid - 1), dfs(i, j - mid))
				if left < right:
					lo = mid + 1
				else:
					hi = mid
			res = 1 + max(dfs(i - 1, lo - 1), dfs(i, j - lo))
			d[i, j] = res
			return res
		d = {}
		return dfs(K, N)


class Solution:

	def superEggDrop(self, K: int, N: int) -> int:
		dp = range(N + 1)
		for k in range(2, K + 1):
			dp2 = [0]
			A = 1
			for n in range(1, N + 1):
				costA = max(dp[A - 1], dp2[n - A])
				while A < n:
					B = A + 1
					costB = max(dp[B - 1], dp2[n - B])
					if costB > costA:
						break
					costA = costB
					A += 1
				dp2.append(1 + costA)
			dp = dp2
		return dp[-1]


class Solution:

	def eggDrop(self, floors, eggs, m):
		if floors <= 1:
			return floors
		if eggs == 1:
			return floors
		if (floors, eggs) in m:
			return m[floors, eggs]
		(l, h) = (0, floors)
		while l < h:
			mid = l + h >> 1
			(kelge, mele) = (self.eggDrop(mid - 1, eggs - 1, m), self.eggDrop(floors - mid, eggs, m))
			if kelge >= mele:
				h = mid
			else:
				l = mid + 1
		drops = 1 + max(self.eggDrop(l - 1, eggs - 1, m), self.eggDrop(floors - l, eggs, m))
		m[floors, eggs] = drops
		return drops

	def superEggDrop(self, K: int, N: int) -> int:
		return self.eggDrop(N, K, {})


class Solution:

	def superEggDrop(self, eggs: int, floors: int) -> int:
		building = [[0] * (eggs + 1) for _ in range(floors + 1)]
		currFloor = 0
		while building[currFloor][eggs] < floors:
			currFloor += 1
			for i in range(1, eggs + 1):
				building[currFloor][i] = building[currFloor - 1][i - 1] + building[currFloor - 1][i] + 1
		return currFloor


class Solution:

	def superEggDrop(self, K: int, N: int) -> int:
		dp = {}

		def num_moves(n, k):
			if (n, k) not in dp:
				if n == 0:
					ans = 0
				elif k == 1:
					ans = n
				else:
					left = 1
					right = n + 1
					while left < right:
						floor = (left + right) // 2
						safe_moves = num_moves(n - floor, k)
						unsafe_moves = num_moves(floor - 1, k - 1)
						if safe_moves > unsafe_moves:
							left = floor + 1
						else:
							right = floor
					floor = left
					safe_moves = num_moves(n - floor, k)
					unsafe_moves = num_moves(floor - 1, k - 1)
					nk_moves = max(safe_moves, unsafe_moves) + 1
					if floor > 1:
						prev_floor = left - 1
						prev_safe_moves = num_moves(n - prev_floor, k)
						prev_unsafe_moves = num_moves(prev_floor - 1, k - 1)
						prev_nk_moves = max(prev_safe_moves, prev_unsafe_moves) + 1
						nk_moves = min(nk_moves, prev_nk_moves)
					ans = nk_moves
				dp[n, k] = ans
			return dp[n, k]
		return num_moves(N, K)


class Solution:

	def superEggDrop(self, K: int, N: int) -> int:
		memo = dict()

		def dp(K, N):
			if (K, N) in memo:
				return memo[K, N]
			if K == 1:
				return N
			if N == 0:
				return 0
			res = sys.maxsize
			(lo, hi) = (1, N)
			while lo <= hi:
				mid = int(lo + (hi - lo) / 2)
				broken = dp(K - 1, mid - 1)
				not_broken = dp(K, N - mid)
				if broken < not_broken:
					lo = mid + 1
					res = min(not_broken + 1, res)
				else:
					hi = mid - 1
					res = min(broken + 1, res)
			memo[K, N] = res
			return res
		return dp(K, N)


class Solution:

	def superEggDrop(self, K: int, N: int) -> int:

		def dfs(e, f):
			if e == 1:
				return f
			if f == 0 or f == 1:
				return f
			if (e, f) in cache:
				return cache[e, f]
			(left, right) = (1, f + 1)
			while left < right:
				mid = left + (right - left) // 2
				(i, j) = (dfs(e - 1, mid - 1), dfs(e, f - mid))
				if i < j:
					left = mid + 1
				else:
					right = mid
			cache[e, f] = 1 + max(dfs(e - 1, left - 1), dfs(e, f - left))
			return cache[e, f]
		cache = dict()
		return dfs(K, N)


class Solution:

	def superEggDrop(self, K: int, N: int) -> int:
		results = [[None for _ in range(N + 1)] for _ in range(K + 1)]

		def dp(K, N):
			if K == 1:
				return N
			if N == 0:
				return 0
			if results[K][N]:
				return results[K][N]
			res = N
			left = 1
			right = N
			while left <= right:
				mid = int((right + left) / 2)
				broken_num = dp(K - 1, mid - 1)
				notbroken_num = dp(K, N - mid)
				if broken_num > notbroken_num:
					right = mid - 1
					res = min(res, broken_num + 1)
				else:
					left = mid + 1
					res = min(res, notbroken_num + 1)
			results[K][N] = res
			return res
		return dp(K, N)


class Solution:

	def superEggDrop(self, K: int, N: int) -> int:
		dp = [[0] * (N + 1) for _ in range(K + 1)]
		for i in range(1, N + 1):
			dp[1][i] = i
		for i in range(2, K + 1):
			s = 1
			for j in range(1, N + 1):
				dp[i][j] = j
				while s < j and dp[i][j - s] > dp[i - 1][s - 1]:
					s += 1
				dp[i][j] = min(dp[i][j], max(dp[i][j - s], dp[i - 1][s - 1]) + 1)
		return dp[K][N]


class Solution:

	def superEggDrop(self, K: int, N: int) -> int:
		num_moves = [n for n in range(N + 1)]
		for k in range(2, K + 1):
			next_num_moves = [0 for _ in range(N + 1)]
			floor = 1
			for n in range(1, N + 1):
				safe_moves = next_num_moves[n - floor]
				unsafe_moves = num_moves[floor - 1]
				nk_moves = 1 + max(safe_moves, unsafe_moves)
				while floor < N:
					next_floor = floor + 1
					next_safe_moves = next_num_moves[n - next_floor]
					next_unsafe_moves = num_moves[next_floor - 1]
					next_nk_moves = 1 + max(next_safe_moves, next_unsafe_moves)
					if next_nk_moves < nk_moves:
						floor = next_floor
						nk_moves = next_nk_moves
					else:
						break
				next_num_moves[n] = nk_moves
			num_moves = next_num_moves
		return num_moves[N]


from math import inf
from typing import List

class Solution:

	def superEggDrop(self, K: int, N: int) -> int:
		self.memo = {}
		return self.rec(K, N)

	def rec(self, i, j):
		if i == 1:
			return j
		if j == 0 or j == 1:
			return j
		if (i, j) in self.memo:
			return self.memo[i, j]
		(lo, hi) = (0, j)
		while lo < hi:
			mid = lo + (hi - lo) // 2
			(left, right) = (self.rec(i - 1, mid - 1), self.rec(i, j - mid))
			if left < right:
				lo = mid + 1
			else:
				hi = mid
		res = 1 + self.max(self.rec(i - 1, lo - 1), self.rec(i, j - lo))
		self.memo[i, j] = res
		return res

	def dp(self, K: int, N: int) -> int:
		dp = [[inf for _ in range(N + 1)] for _ in range(K + 1)]
		for i in range(K + 1):
			dp[i][0] = 0
			dp[i][1] = 1
		for j in range(N + 1):
			dp[1][j] = j
		for i in range(2, K + 1):
			for j in range(2, N + 1):
				(left, right) = (0, j)
				while left < right:
					mid = left + (right - left) // 2
					if dp[i - 1][mid - 1] < dp[i][j - mid]:
						left = mid + 1
					else:
						right = mid
				dp[i][j] = 1 + self.max(dp[i - 1][left - 1], dp[i][j - left])
		return dp[K][N]

	def min(self, a, b):
		return a if a < b else b

	def max(self, a, b):
		return a if a > b else b


class Solution:

	def superEggDrop(self, K: int, N: int) -> int:
		table = dict()

		def dp(K: int, N: int) -> int:
			if K == 1:
				return N
			if N <= 0:
				return 0
			if (K, N) in table:
				return table[K, N]
			lo = 1
			hi = N
			while lo <= hi:
				mid = lo + (hi - lo) // 2
				up = dp(K, N - mid)
				dn = dp(K - 1, mid - 1)
				if up >= dn:
					lo = mid + 1
				else:
					hi = mid - 1
			table[K, N] = 1 + min(dp(K, N - hi), dp(K - 1, lo - 1))
			return table[K, N]
		return dp(K, N)


class Solution:

	def superEggDrop(self, K: int, N: int) -> int:
		memo = [[0] * (K + 1) for _ in range(N + 1)]
		for m in range(1, N + 1):
			for k in range(1, K + 1):
				memo[m][k] = memo[m - 1][k - 1] + 1 + memo[m - 1][k]
				if memo[m][k] >= N:
					return m


class Solution:

	def superEggDrop(self, K: int, N: int) -> int:

		def dp(k, n):
			if k == 1:
				return n
			if n == 0:
				return 0
			if (k, n) in memo:
				return memo[k, n]
			res = sys.maxsize
			(lo, hi) = (1, n)
			while lo <= hi:
				mid = (lo + hi) // 2
				broken = dp(k - 1, mid - 1)
				safe = dp(k, n - mid)
				if broken > safe:
					hi = mid - 1
					res = min(res, broken + 1)
				else:
					lo = mid + 1
					res = min(res, safe + 1)
			memo[k, n] = res
			return res
		memo = {}
		return dp(K, N)


class Solution:

	def superEggDrop(self, K: int, N: int) -> int:
		cache = {}

		def drop(egg, floor):
			if egg == 1 or floor <= 1:
				return floor
			if (egg, floor) in cache:
				return cache[egg, floor]
			minAttempts = float('inf')
			l = 1
			h = floor
			while l <= h:
				mid = (l + h) // 2
				low = drop(egg - 1, mid - 1)
				high = drop(egg, floor - mid)
				attempts = 1 + max(low, high)
				if low < high:
					l = mid + 1
				else:
					h = mid - 1
				minAttempts = min(minAttempts, attempts)
			cache[egg, floor] = minAttempts
			return minAttempts
		return drop(K, N)


class Solution(object):

	def superEggDrop(self, K, N):
		memo = {}

		def dp(K, N):
			if K == 1:
				return N
			if N == 0:
				return 0
			if (K, N) in memo:
				return memo[K, N]
			res = float('INF')
			(lo, hi) = (1, N)
			while lo <= hi:
				mid = (lo + hi) // 2
				broken = dp(K - 1, mid - 1)
				not_broken = dp(K, N - mid)
				if broken > not_broken:
					hi = mid - 1
					res = min(res, broken + 1)
				else:
					lo = mid + 1
					res = min(res, not_broken + 1)
			memo[K, N] = res
			return res
		return dp(K, N)


class Solution:

	def superEggDrop(self, K: int, N: int) -> int:
		dp = [[sys.maxsize for i in range(N + 1)] for j in range(K + 1)]

		def DP(k, n):
			if k < 0 or n < 0:
				return 0
			if k == 0:
				return 0
			if k == 1:
				return n
			if n == 0:
				return 0
			if n == 1:
				return 1
			if dp[k][n] != sys.maxsize:
				return dp[k][n]
			l = 0
			r = n
			while l < r:
				m = (l + r) // 2
				if DP(k - 1, m - 1) >= DP(k, n - m):
					r = m
				else:
					l = m + 1
			dp[k][n] = 1 + max(DP(k - 1, l - 1), DP(k, n - l))
			return dp[k][n]
		return DP(K, N)


class Solution:

	def superEggDrop(self, K: int, N: int) -> int:

		def dfs(k, n, memo):
			if k == 1:
				return n
			if n == 0:
				return 0
			if (k, n) in memo:
				return memo[k, n]
			res = float('inf')
			(lo, hi) = (1, n)
			while lo <= hi:
				mid = (lo + hi) // 2
				broken = dfs(k - 1, mid - 1, memo)
				no_broken = dfs(k, n - mid, memo)
				if broken > no_broken:
					hi = mid - 1
					res = min(res, broken + 1)
				else:
					lo = mid + 1
					res = min(res, no_broken + 1)
			memo[k, n] = res
			return res
		return dfs(K, N, {})


class Solution:

	def superEggDrop(self, K: int, N: int) -> int:

		def f(x):
			ans = 0
			r = 1
			for i in range(1, K + 1):
				r *= (x - i + 1) / i
				ans += r
				if ans >= N:
					break
			return ans
		(low, high) = (1, N)
		while low < high:
			middle = (low + high) // 2
			if f(middle) < N:
				low = middle + 1
			else:
				high = middle
		return low


class Solution:

	def superEggDrop(self, K: int, N: int) -> int:
		dp_dict = dict()

		def dp(K, N):
			if K == 1:
				return N
			if N == 0:
				return 0
			if (K, N) in dp_dict:
				return dp_dict[K, N]
			ans = inf
			(low, high) = (1, N)
			while low <= high:
				mid = (high + low) // 2
				broken = dp(K - 1, mid - 1)
				good = dp(K, N - mid)
				if broken > good:
					high = mid - 1
					ans = min(broken + 1, ans)
				else:
					low = mid + 1
					ans = min(good + 1, ans)
			dp_dict[K, N] = ans
			return ans
		return dp(K, N)


class Solution:

	def superEggDrop(self, K: int, N: int) -> int:
		memo = dict()

		def dp(K, N):
			if K == 1:
				return N
			if N == 0:
				return 0
			if (K, N) in memo:
				return memo[K, N]
			res = float('inf')
			(low, high) = (1, N + 1)
			while low < high:
				mid = (low + high) // 2
				broken = dp(K - 1, mid - 1)
				notBroken = dp(K, N - mid)
				if broken > notBroken:
					high = mid
					res = min(broken + 1, res)
				else:
					low = mid + 1
					res = min(notBroken + 1, res)
			memo[K, N] = res
			return res
		return dp(K, N)


class Solution:

	def superEggDrop(self, K: int, N: int) -> int:
		DP = range(N + 1)
		for k in range(2, K + 1):
			DP2 = [0]
			x = 1
			for n in range(1, N + 1):
				while x < n and max(DP[x - 1], DP2[n - x]) > max(DP[x], DP2[n - x - 1]):
					x += 1
				DP2.append(1 + max(DP[x - 1], DP2[n - x]))
			DP = DP2
		return DP[-1]


class Solution:

	def superEggDrop(self, K: int, N: int) -> int:
		memo = {}

		def dp(K, N):
			if K == 1:
				return N
			if N == 0:
				return 0
			if (K, N) in memo:
				return memo[K, N]
			res = float('inf')
			(l, h) = (1, N)
			while l <= h:
				mid = (l + h) // 2
				broken = dp(K - 1, mid - 1)
				not_broken = dp(K, N - mid)
				if broken > not_broken:
					h = mid - 1
					res = min(res, 1 + broken)
				else:
					l = mid + 1
					res = min(res, 1 + not_broken)
			memo[K, N] = res
			return res
		return dp(K, N)


class Solution:

	def superEggDrop(self, K: int, N: int) -> int:
		t = [[0] * (K + 1) for _ in range(N + 1)]
		for i in range(1, N + 1):
			for j in range(1, K + 1):
				t[i][j] = t[i - 1][j] + t[i - 1][j - 1] + 1
			if t[i][j] >= N:
				return i


class Solution:

	def superEggDrop(self, K: int, N: int) -> int:
		dp = [[None] * K for _ in range(N + 1)]
		for j in range(K):
			dp[0][j] = 0
		for i in range(1, N + 1):
			dp[i][0] = i
		for j in range(1, K):
			dp[1][j] = 1
			m = 1
			for i in range(2, N + 1):
				while m < i and dp[i - m][j] >= dp[m - 1][j - 1] and (dp[i - m - 1][j] >= dp[m][j - 1]):
					m += 1
				dp[i][j] = max(dp[i - m][j], dp[m - 1][j - 1]) + 1
		return dp[N][K - 1]


class Solution:

	def superEggDrop(self, K: int, N: int) -> int:
		dp = list(range(N + 1))
		for k in range(1, K):
			newdp = [0]
			opt = 1
			for n in range(1, N + 1):
				tmp = max(dp[opt - 1], newdp[n - opt])
				while opt < n and tmp > max(dp[opt], newdp[n - opt - 1]):
					tmp = max(dp[opt], newdp[n - opt - 1])
					opt += 1
				newdp.append(1 + tmp)
			dp = newdp
		return dp[-1]


class Solution:

	def superEggDrop(self, K: int, N: int) -> int:
		cache = {}
		return self.drop_iter(K, N, cache)

	def drop_iter(self, K, N, cache):
		if K == 1:
			return N
		if N == 0:
			return 0
		if (K, N) in cache:
			return cache[K, N]
		res = float('inf')
		left = 1
		right = N
		while left <= right:
			mid = (left + right) // 2
			borke = self.drop_iter(K - 1, mid - 1, cache)
			not_broke = self.drop_iter(K, N - mid, cache)
			if borke > not_broke:
				right = mid - 1
				res = min(borke + 1, res)
			else:
				left = mid + 1
				res = min(not_broke + 1, res)
		cache[K, N] = res
		return res


class Solution:

	def superEggDrop(self, K: int, N: int) -> int:
		dp = range(N + 1)
		for k in range(2, K + 1):
			dp2 = [0]
			x = 1
			for n in range(1, N + 1):
				while x < n and max(dp[x - 1], dp2[n - x]) > max(dp[x], dp2[n - x - 1]):
					x += 1
				dp2.append(1 + max(dp[x - 1], dp2[n - x]))
			dp = dp2
		return dp[-1]


class Solution:

	def superEggDrop(self, K: int, N: int) -> int:
		m = [[0 for i in range(N + 1)] for j in range(K + 1)]

		def find(k, n):
			if k == 1:
				return n
			if n == 0:
				return 0
			if m[k][n] > 0:
				return m[k][n]

			def bsearch():
				(st, end) = (1, n)
				while st <= end:
					m = (st + end) // 2
					if predicate(m):
						end = m - 1
					else:
						st = m + 1
				return (st, end)

			def predicate(x):
				return True if find(k - 1, x - 1) >= find(k, n - x) else False
			(st, end) = bsearch()
			v_st = max(find(k - 1, st - 1), find(k, n - st)) if st <= N else math.inf
			v_end = max(find(k - 1, end - 1), find(k, n - end)) if end >= 1 else math.inf
			m[k][n] = min(v_st, v_end) + 1
			return m[k][n]
		return find(K, N)


class Solution:

	def superEggDrop(self, K: int, N: int) -> int:
		cachedSolutions = [[-1 for i in range(N + 1)] for j in range(K + 1)]
		return self.getMinDrops(K, N, cachedSolutions)

	def getMinDrops(self, eggs, floors, cachedSolutions):
		if cachedSolutions[eggs][floors] > 0:
			return cachedSolutions[eggs][floors]
		elif eggs == 0:
			cachedSolutions[eggs][floors] = 0
			return 0
		elif eggs == 1 or floors <= 2:
			cachedSolutions[eggs][floors] = floors
			return floors
		else:
			smallestIndex = 1
			largestIndex = floors
			minDrops = 100000000
			while smallestIndex <= largestIndex:
				middleIndex = round(smallestIndex + (largestIndex - smallestIndex) / 2)
				minDropsA = self.getMinDrops(eggs - 1, middleIndex - 1, cachedSolutions)
				minDropsB = self.getMinDrops(eggs, floors - middleIndex, cachedSolutions)
				tempMinDrops = max(minDropsA, minDropsB) + 1
				minDrops = min(minDrops, tempMinDrops)
				if minDropsA > minDropsB:
					largestIndex = middleIndex - 1
				else:
					smallestIndex = middleIndex + 1
			cachedSolutions[eggs][floors] = minDrops
		return cachedSolutions[eggs][floors]


class Solution:

	def superEggDrop(self, K: int, N: int) -> int:
		dp = [[0] * (K + 1) for _ in range(N + 1)]
		for move in range(1, N + 1):
			for egg in range(1, K + 1):
				dp[move][egg] = dp[move - 1][egg - 1] + dp[move - 1][egg] + 1
			if dp[move][K] >= N:
				return move


from scipy.special import comb, factorial, hyp2f1
from math import log2, floor

def h(k, n):
	return round(2 ** n - 1 - comb(n, k + 1) * hyp2f1(1, k - n + 1, k + 2, -1))

def h2(k, n):
	return sum((comb(n, j) for j in range(1, k + 1)))

def fast_sum(k, l):
	s = 0
	c = 1
	for i in range(1, k + 1):
		c *= (l - i + 1) / i
		s += c
	return s

def e(k, n):
	if k == 1:
		return n
	return sum((e(k - 1, j) + 1 for j in range(n)))

def f(K, x):
	ans = 0
	r = 1
	for i in range(1, K + 1):
		r *= x - i + 1
		r //= i
		ans += r
	return ans

class Solution:

	def superEggDrop(self, k: int, n: int) -> int:
		if k == 0:
			return n
		(a, b) = (1, n)
		while a < b:
			c = (a + b) // 2
			if fast_sum(k, c) < n:
				a = c + 1
			else:
				b = c
		return a


class Solution:

	def superEggDrop(self, K: int, N: int) -> int:
		dp = [[0 for _ in range(N + 1)] for _ in range(K + 1)]
		m = 0
		while dp[K][m] < N:
			m += 1
			for k in range(1, K + 1):
				dp[k][m] = dp[k - 1][m - 1] + dp[k][m - 1] + 1
		return m


class Solution:

	def superEggDrop(self, K, N):
		dp = [0, 0]
		m = 0
		while dp[-1] < N:
			for i in range(len(dp) - 1, 0, -1):
				dp[i] += dp[i - 1] + 1
			if len(dp) < K + 1:
				dp.append(dp[-1])
			m += 1
		return m


class Solution:

	def superEggDrop(self, K: int, N: int) -> int:
		dp = [[0 for col in range(N + 2)] for row in range(K + 2)]
		m = 0
		while dp[K][m] < N:
			m += 1
			for k in range(1, K + 1):
				dp[k][m] = dp[k - 1][m - 1] + dp[k][m - 1] + 1
		return m


from scipy.special import comb, factorial, hyp2f1
from math import log2, floor

def h(k, n):
	return round(2 ** n - 1 - comb(n, k + 1) * hyp2f1(1, k - n + 1, k + 2, -1))

def h2(k, n):
	return sum((comb(n, j) for j in range(1, k + 1)))

def e(k, n):
	if k == 1:
		return n
	return sum((e(k - 1, j) + 1 for j in range(n)))

class Solution:

	def superEggDrop(self, k: int, n: int) -> int:
		l = 0
		while h2(k, l) < n:
			l += 1
		return l


class Solution:

	def superEggDrop(self, K: int, N: int) -> int:
		(dp, ndp) = ({}, {})
		for m in range(1, N + 1):
			for k in range(1, K + 1):
				if m == 1:
					ndp[k] = 1
				elif k == 1:
					ndp[k] = m
				else:
					ndp[k] = dp[k - 1] + dp[k] + 1
				if ndp[k] >= N:
					return m
			(dp, ndp) = (ndp, {})


from math import comb

class Solution:

	def ncr(self, n, r):
		sum = 0
		r = min(n, r)
		for l in range(1, r + 1):
			sum += comb(n, l)
		return sum

	def superEggDrop(self, K, N):
		matrix = [[0 for j in range(K)] for i in range(N)]
		for i in range(N):
			for j in range(K):
				matrix[i][j] = self.ncr(i + 1, j + 1)
				if matrix[i][K - 1] >= N:
					return i + 1
		print(matrix)


class Solution:

	def superEggDrop(self, K: int, N: int) -> int:
		dp = [[0 for _ in range(K + 1)] for _ in range(N + 1)]
		attempt = 0
		while dp[attempt][K] < N:
			attempt += 1
			for i in range(1, K + 1):
				dp[attempt][i] = 1 + dp[attempt - 1][i - 1] + dp[attempt - 1][i]
				if dp[attempt][i] >= N:
					return attempt
		return attempt


class Solution:

	def superEggDrop(self, K: int, N: int) -> int:
		dp = [[0 for _ in range(K + 1)] for _ in range(N + 1)]
		for n in range(1, N + 1):
			for k in range(1, K + 1):
				dp[n][k] = 1 + dp[n - 1][k] + dp[n - 1][k - 1]
			if dp[n][K] >= N:
				return n


class Solution:

	def superEggDrop(self, K: int, N: int) -> int:

		def dp(m, k):
			if m <= 1 or k == 1:
				return m
			if (m, k) in memo:
				return memo[m, k]
			memo[m, k] = dp(m - 1, k - 1) + 1 + dp(m - 1, k)
			return memo[m, k]
		memo = {}
		for i in range(N + 1):
			if dp(i, K) >= N:
				return i


class Solution:

	def superEggDrop(self, K: int, N: int) -> int:
		drops = 0
		floors = [0] * (K + 1)
		while floors[K] < N:
			for eggs in range(K, 0, -1):
				floors[eggs] += 1 + floors[eggs - 1]
			drops += 1
		return drops

	def superEggDrop(self, K: int, N: int) -> int:
		M = N
		dp = [[0 for j in range(K + 1)] for i in range(M + 1)]
		for i in range(1, M + 1):
			for j in range(1, K + 1):
				dp[i][j] = 1 + dp[i - 1][j] + dp[i - 1][j - 1]
				if dp[i][j] >= N:
					return i


import numpy as np

class Solution:

	def superEggDrop(self, K: int, N: int) -> int:
		dp = [[0 for i in range(K + 1)] for j in range(N + 1)]
		for i in range(1, N + 1):
			for j in range(1, K + 1):
				dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j] + 1
			if dp[i][j] >= N:
				return i


from functools import lru_cache
from typing import Tuple

class Solution:

	def superEggDrop(self, K: int, N: int) -> int:
		return superEggHelper(K, N)

@lru_cache(maxsize=None)
def superEggHelper(K: int, N: int) -> int:
	if N == 0:
		return 0
	if K == 1:
		return N
	ans = bisectEggHelper(K, 1, N, N)
	return ans

def bisectEggHelper(K: int, S: int, E: int, N: int) -> int:
	if S == E:
		(left, right) = superEggCalc(K, S, N)
		return max(left, right) + 1
	if S + 1 == E:
		(left1, right1) = superEggCalc(K, S, N)
		(left2, right2) = superEggCalc(K, E, N)
		return min(max(left1, right1), max(left2, right2)) + 1
	i = (S + E) // 2
	(left, right) = superEggCalc(K, i, N)
	if left > right:
		return bisectEggHelper(K, S, i, N)
	else:
		return bisectEggHelper(K, i, E, N)

def superEggCalc(K: int, i: int, N: int) -> Tuple:
	return (superEggHelper(K - 1, i - 1), superEggHelper(K, N - i))


class Solution:

	def superEggDrop(self, K: int, N: int) -> int:
		dp = list(range(1, N + 1))
		for _ in range(K - 1):
			temp = [1]
			for j in range(1, N):
				if temp[-1] >= N:
					break
				temp.append(temp[-1] + dp[j - 1] + 1)
			dp = temp
		return len(dp)


class Solution:

	@lru_cache(None)
	def superEggDrop(self, k: int, n: int) -> int:
		if n == 0:
			return 0
		elif k == 1:
			return n
		(lo, hi) = (1, n)
		while lo < hi:
			mid = (lo + hi) // 2
			(r1, r2) = (self.superEggDrop(k - 1, mid - 1), self.superEggDrop(k, n - mid))
			if r1 > r2:
				hi = mid
			elif r1 < r2:
				lo = mid + 1
			else:
				lo = hi = mid
		return 1 + max(self.superEggDrop(k - 1, lo - 1), self.superEggDrop(k, n - lo))


class Solution:

	def superEggDrop(self, K: int, N: int) -> int:

		@lru_cache(None)
		def helper(floors, eggs):
			if floors <= 0:
				return 0
			if eggs == 1:
				return floors
			ans = floors
			(low, high) = (1, floors)
			while low + 1 < high:
				mid = low + (high - low) // 2
				t1 = helper(mid - 1, eggs - 1)
				t2 = helper(floors - mid, eggs)
				if t1 < t2:
					low = mid
				elif t1 > t2:
					high = mid
				else:
					low = high = mid
			ans = floors
			for k in (low, high):
				ans = min(ans, 1 + max(helper(k - 1, eggs - 1), helper(floors - k, eggs)))
			return ans
		return helper(N, K)


from functools import lru_cache

class Solution:

	def superEggDrop(self, K: int, N: int) -> int:

		@lru_cache(maxsize=None)
		def dp(K: int, N: int) -> int:
			if N == 0:
				return 0
			elif K == 1:
				return N
			else:
				(l, r) = (1, N)
				res = N
				while l + 1 < r:
					X = (l + r) // 2
					f1 = dp(K, N - X)
					f2 = dp(K - 1, X - 1)
					if f1 < f2:
						r = X
					elif f1 == f2:
						l = r = X
					else:
						l = X
				return 1 + min((max(dp(K - 1, X - 1), dp(K, N - X)) for X in (l, r)))
		return dp(K, N)


t = [[-1 for i in range(10001)] for j in range(101)]

class Solution:

	def superEggDrop(self, K: int, N: int) -> int:
		if N == 0 or N == 1:
			return N
		if K == 1:
			return N
		if t[K][N] != -1:
			return t[K][N]
		(mn, l, h) = (sys.maxsize, 1, N)
		while l <= h:
			mid = (l + h) // 2
			down_temp = self.superEggDrop(K - 1, mid - 1)
			up_temp = self.superEggDrop(K, N - mid)
			res = 1 + max(down_temp, up_temp)
			if down_temp < up_temp:
				l = mid + 1
			else:
				h = mid - 1
			mn = min(mn, res)
		t[K][N] = mn
		return mn


class Solution:

	def superEggDrop(self, K: int, N: int) -> int:
		dict_soln = {}
		return self.dp(K, N, dict_soln)

	def dp(self, k, n, dict_soln):
		if n == 0:
			return 0
		if k == 0:
			return -1
		if k == 1:
			return n
		if (k, n) in dict_soln:
			return dict_soln[k, n]
		left = 1
		right = n
		while True:
			if left - right == -1:
				tmp1 = self.dp(k - 1, left - 1, dict_soln)
				tmp2 = self.dp(k, n - left, dict_soln)
				tmp3 = self.dp(k - 1, right - 1, dict_soln)
				tmp4 = self.dp(k, n - right, dict_soln)
				tmpl = max(tmp1, tmp2)
				tmpr = max(tmp3, tmp4)
				if tmpl < tmpr:
					dict_soln[k, n] = tmpl + 1
					return dict_soln[k, n]
				else:
					dict_soln[k, n] = tmpr + 1
					return dict_soln[k, n]
			xmid = (left + right) // 2
			tmp1 = self.dp(k - 1, xmid - 1, dict_soln)
			tmp2 = self.dp(k, n - xmid, dict_soln)
			if tmp1 > tmp2:
				right = xmid
			elif tmp1 < tmp2:
				left = xmid
			else:
				dict_soln[k, n] = tmp1 + 1
				return dict_soln[k, n]


class Solution:

	def superEggDrop(self, K: int, N: int) -> int:
		memo = {}

		def dp(k, n):
			if (k, n) in memo:
				return memo[k, n]
			if k == 1:
				return n
			if n == 0:
				return 0
			start = 1
			end = n
			res = float('inf')
			while start <= end:
				mid = (start + end) // 2
				pre = dp(k - 1, mid - 1) + 1
				cur = dp(k, n - mid) + 1
				if pre < cur:
					res = min(res, cur)
					start = mid + 1
				elif pre > cur:
					res = min(res, pre)
					end = mid - 1
				else:
					res = pre
					break
			memo[k, n] = res
			return res
		return dp(K, N)


class Solution:

	def superEggDrop(self, K: int, N: int) -> int:
		dp = list(range(1, N + 1))
		for _ in range(K - 1):
			temp = [1]
			for j in range(1, N):
				temp.append(temp[-1] + dp[j - 1] + 1)
			dp = temp
		return [i + 1 for (i, x) in enumerate(dp) if x >= N][0]


from functools import lru_cache

class Solution:

	def superEggDrop(self, K: int, N: int) -> int:
		return self.bottomUp2(K, N)

	@lru_cache(maxsize=None)
	def findMoves(self, K, N):
		if K == 1 or N <= 1:
			return N
		(left, right) = (1, N)
		while left < right:
			mid = (left + right) // 2
			broken = self.findMoves(K - 1, mid - 1)
			intact = self.findMoves(K, N - mid)
			if broken > intact:
				right = mid
			else:
				left = mid + 1
		mid = left - 1
		return 1 + max(self.findMoves(K - 1, mid - 1), self.findMoves(K, N - mid))

	def bottomUp(self, K, N):
		dp = [i for i in range(N + 1)]
		for i in range(2, K + 1):
			prev = dp[:]
			for j in range(1, N + 1):
				min_drops = N
				for x in range(1, j + 1):
					min_drops = min(min_drops, 1 + max(prev[x - 1], dp[j - x]))
				dp[j] = min_drops
		print(dp)
		return dp[N]

	def bottomUp2(self, K, N):
		dp = [i for i in range(N + 1)]
		for i in range(2, K + 1):
			broken = dp[1]
			for i in range(2, N + 1):
				prev = dp[i]
				dp[i] = 1 + dp[i - 1] + broken
				broken = prev
		(left, right) = (1, N)
		while left < right:
			mid = (left + right) // 2
			if dp[mid] >= N:
				right = mid
			left = left + 1
		return left


class Solution(object):

	def superEggDrop(self, K, N):
		memo = {}

		def dp(k, n):
			if (k, n) not in memo:
				if n == 0 or n == 1:
					ans = n
				elif k == 1:
					ans = n
				else:
					(lo, hi) = (1, n)
					while lo + 1 < hi:
						x = (lo + hi) // 2
						t1 = dp(k - 1, x - 1)
						t2 = dp(k, n - x)
						if t1 < t2:
							lo = x
						elif t1 > t2:
							hi = x
						else:
							lo = hi = x
					ans = 1000000
					for x in range(lo, hi + 1):
						temp = 1 + max(dp(k - 1, x - 1), dp(k, n - x))
						if ans > temp:
							ans = temp
				memo[k, n] = ans
			return memo[k, n]
		return dp(K, N)


class Solution:

	def superEggDrop(self, K, N):
		dp = dict()

		def recursive(k, n):
			if k == 1:
				return n
			if n == 0:
				return 0
			if (k, n) in dp:
				return dp[k, n]
			res = float('INF')
			l = 1
			r = n + 1
			while l <= r:
				m = int((l + r) / 2)
				v1 = recursive(k, n - m)
				v2 = recursive(k - 1, m - 1)
				res = min(res, max(v1, v2) + 1)
				if v1 < v2:
					r = m - 1
				elif v1 > v2:
					l = m + 1
				else:
					break
			dp[k, n] = res
			return res
		import sys
		sys.setrecursionlimit(3000)
		res = recursive(K, N)
		return res


class Solution:

	def superEggDrop(self, K: int, N: int) -> int:
		dp = {}

		def helper(K, N):
			if N <= 2:
				return N
			if K == 1:
				return N
			if (K, N) not in dp:
				l = 1
				r = N
				while l + 1 < r:
					mid = (l + r) // 2
					die = helper(K - 1, mid - 1)
					live = helper(K, N - mid)
					if die < live:
						l = mid
					elif die > live:
						r = mid
					else:
						l = r = mid
				dp[K, N] = 1 + min([max(helper(K - 1, l - 1), helper(K, N - l)), max(helper(K - 1, r - 1), helper(K, N - r))])
			return dp[K, N]
		return helper(K, N)


class Solution:

	def __init__(self):
		self.memo = {}

	def superEggDrop(self, K: int, N: int) -> int:

		def solve(K, N):
			d = self.memo.get((K, N))
			if d is None:
				if K == 1 or N <= 2:
					d = N
				else:
					A_min = 1
					A_max = N
					while A_max - A_min > 1:
						A = (A_min + A_max) // 2
						t1 = solve(K - 1, A - 1)
						t2 = solve(K, N - A)
						if t1 > t2:
							A_max = A
						elif t2 > t1:
							A_min = A
						else:
							A_min = A_max = A
					d = 1 + min((max(self.memo[K - 1, A - 1], self.memo[K, N - A]) for A in [A_min, A_max]))
				self.memo[K, N] = d
			return d
		return solve(K, N)


from math import floor, log2

class Solution:

	def superEggDrop(self, k: int, n: int) -> int:
		best_case = floor(log2(n) + 1)
		if k >= best_case:
			return best_case

		def fast_sum(k, l):
			s = 0
			c = 1
			for i in range(k):
				c *= (l - i) / (i + 1)
				s += c
			return s
		if k == 0:
			return n
		(a, b) = (1, n)
		while a < b:
			c = (a + b) // 2
			if fast_sum(k, c) < n:
				a = c + 1
			else:
				b = c
		return a


class Solution:

	def superEggDrop(self, K: int, N: int) -> int:
		INF = N + 1
		cache = {}

		def eggDropHelper(k, n):
			if (k, n) in cache:
				return cache[k, n]
			if k < 0:
				return INF
			if n == 0:
				return 0
			if k == 0:
				return INF
			optAns = INF
			(l, r) = (1, n)
			while l + 1 < r:
				m = (l + r) // 2
				(left, right) = (eggDropHelper(k - 1, m - 1), eggDropHelper(k, n - m))
				if left < right:
					l = m
				elif left > right:
					r = m
				else:
					l = r = m
					break
			optAns = max(eggDropHelper(k - 1, l - 1), eggDropHelper(k, n - l)) + 1
			currAns = max(eggDropHelper(k - 1, r - 1), eggDropHelper(k, n - r)) + 1
			optAns = min(currAns, optAns)
			cache[k, n] = optAns
			return cache[k, n]
		return eggDropHelper(K, N)