<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:
        # To solve F(n, k): min num of operations needed
        # to decide f.
        # Iterate through all the floors from 0 to n.
        # case_1: the egg breaks.
        # F(i-1, k-1)
        # case_2: the egg survives.
        # F(n-i, k)
        # Combining two cases, we need to take the max.
        @cache
        def F(x, y):
            # Ensure y >= 1.
            if y == 1:
                return x
            if x <= 0:
                return 0
            mn = x
            # This will time out.
            # for i in range(1, x+1):
            #     mn = min(1 + max(F(i-1, y-1), F(x-i, y)), mn)
            # Notice that F(x, y) increases with x: the higher
            # the floor, the more attempts we need.
            # Therefore, when i increases, F1 = F(i-1, y-1) increases,
            # and F2 = F(x-i, y) decreases.
            # To find the minimum of max(F1, F2), it is the intersection
            # of F1 and F2.
            # At some point z,
            # if F1(z) > F2(z), then we should search in [z, x];
            # if F1(z) < F2(z), then we should search in [1, z].
            l, r = 1, x
            while l + 1 < r:
                m = (l+r)//2
                F1 = F(m-1, y-1)
                F2 = F(x-m, y)
                if F1 < F2:
                    l = m
                elif F1 > F2:
                    r = m
                else:
                    l = r = m
            for i in range(l, r+1):
                mn = min(1 + max(F(i-1, y-1), F(x-i, y)), mn)
            return mn

        return F(n, k)
26610