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
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
            # if it breaks;
            r1 = 1 + self.cal_eggs(K - 1, mid - 1)
            # if it not breaks;
            r2 = 1 + self.cal_eggs(K, N - mid)

            if r1 == r2:
                return mid
            elif r1 < r2:
                left = mid + 1
            else:
                right = mid - 1

        return right

    def cal_eggs(self, K, N):
        # print(K,N)
        if N == 0: return 0
        if K == 1: return N

        if (K, N) not in self.memo:
            r = 2 ** 32 - 1
            now_floor = self.find_that_floor(K,N)
            for floor in range(now_floor, min(now_floor + 2,N+1)):
                # if it breaks;
                r1 = 1 + self.cal_eggs(K - 1, floor - 1)
                # if it not breaks;
                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:
        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
            # if it breaks;
            r1 = 1 + self.cal_eggs(K - 1, mid - 1)
            # if it not breaks;
            r2 = 1 + self.cal_eggs(K, N - mid)

            if r1 == r2:
                return mid
            elif r1 < r2:
                left = mid + 1
            else:
                right = mid - 1

        return right

    def cal_eggs(self, K, N):
        # print(K,N)
        if N == 0: return 0
        if K == 1: return N

        if (K, N) not in self.memo:
            r = 2 ** 32 - 1
            now_floor = self.find_that_floor(K,N)
            for floor in range(now_floor, min(now_floor + 2,N+1)):
                # if it breaks;
                r1 = 1 + self.cal_eggs(K - 1, floor - 1)
                # if it not breaks;
                r2 = 1 + self.cal_eggs(K, N - floor)

                r = min(r, max(r1, r2))

            self.memo[(K, N)] = r

        return self.memo[(K, N)]
