<p>You are given <code>k</code> identical eggs and you have access to a building with <code>n</code> floors labeled from <code>1</code> to <code>n</code>.</p>

<p>You know that there exists a floor <code>f</code> where <code>0 &lt;= f &lt;= n</code> such that any egg dropped at a floor <strong>higher</strong> than <code>f</code> will <strong>break</strong>, and any egg dropped <strong>at or below</strong> floor <code>f</code> will <strong>not break</strong>.</p>

<p>Each move, you may take an unbroken egg and drop it from any floor <code>x</code> (where <code>1 &lt;= x &lt;= n</code>). If the egg breaks, you can no longer use it. However, if the egg does not break, you may <strong>reuse</strong> it in future moves.</p>

<p>Return <em>the <strong>minimum number of moves</strong> that you need to determine <strong>with certainty</strong> what the value of </em><code>f</code> is.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> k = 1, n = 2
<strong>Output:</strong> 2
<strong>Explanation: </strong>
Drop the egg from floor 1. If it breaks, we know that f = 0.
Otherwise, drop the egg from floor 2. If it breaks, we know that f = 1.
If it does not break, then we know f = 2.
Hence, we need at minimum 2 moves to determine with certainty what the value of f is.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> k = 2, n = 6
<strong>Output:</strong> 3
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> k = 3, n = 14
<strong>Output:</strong> 4
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= k &lt;= 100</code></li>
	<li><code>1 &lt;= n &lt;= 10<sup>4</sup></code></li>
</ul>

class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        
        
        
        # public solution ... 124 ms ... 41 % ... 20.8 MB .. 0 %
        #  time: O(N*K)
        # space: O(N*K)
        """
        dp 表示能达到的楼层，最坏情况是 N 次，不可能超过 N 次。
        所以可以从 1 到 N 遍历【还可进一步优化为二分查找】
        """
        # dp = [[0]*(K+1) for _ in range(N+1)]  # dp[step][egg_used] 表示在第 step 次操作时，使用 egg_used 个鸡蛋可达到的最高层数
        # for step in range(1, N+1):
        #     for egg_used in range(1, K+1):
        #         dp[step][egg_used] = dp[step-1][egg_used-1] + dp[step-1][egg_used] + 1  # 前一项表示破了，后一项表示没破
        #         if dp[step][egg_used] >= N:
        #             return step
        
        
        
        # my solution following public discussion ... 730 ms ... 30 % ... 20 MB ... 0 %
        #  time: O(K*N*logN)
        # space: O(K*N*logN)
        
        seen = {}
        def func(lower, upper, count):   # 返回从 lower ~ upper 中，使用 count 个鸡蛋，找到 F 所需的最小步数【lower 肯定不碎，upper 肯定碎】
            if lower + 1 == upper:
                return 0
            if count == 1:
                return upper - lower - 1
            if (upper - lower, count) not in seen:
                
                # res = float('inf')       # brutal ... TLE
                # for m in range(lower + 1, upper):
                #     cur = 1 + max(func(lower, m, count-1), func(m, upper, count))  # 前者为 m 增函数，后者为 m 减函数
                #     res = min(res, cur)                                            # 固定 m 取它俩 max，然后改变 m 取所有 max 的 min
                                                                                     # 因为上述函数单调关系，故 cur(m) 函数是 V 字形
                s, e = lower + 1, upper  # 730 ms ... 30 % ... 20 MB ... 0 %
                while s + 1 < e:
                    m = (s + e) // 2
                    broken, not_broken = func(lower, m, count-1), func(m, upper, count)
                    if broken == not_broken:
                        s, e = m, m
                        break
                    elif broken < not_broken:
                        s = m
                    else:
                        e = m
                
                # s, e = lower + 1, upper  # 2600 ms ... 13 % ... 34.3 MB ... 0 %
                # while s < e:
                #     m = (s + e) // 2
                #     broken, not_broken = func(lower, m, count-1), func(m, upper, count)
                #     if broken < not_broken:
                #         s = m + 1
                #     else:
                #         e = m
                
                seen[upper - lower, count] = 1 + max(func(lower, s, count-1), func(s, upper, count))
            return seen[upper - lower, count]
        return func(0, N+1, K)
        
        
        
        
        
        
23539