820. Egg Drop Problem (Recursive + Memo)

Given k eggs and n floors, find the minimum number of trials needed in the worst case to determine the critical floor. Use the binary-search + combinatorial approach.

Input: Two integers k (eggs) and n (floors).

Output: Integer.

Examples

Input: 1, 10
Output: 10
Explanation: With 1 egg, must try each floor.

Input: 2, 10
Output: 4
Explanation: 4 trials suffice with 2 eggs, 10 floors.

Input: 2, 6
Output: 3
Explanation: 3 trials.

Constraints

• 1 <= k <= 100
• 0 <= n <= 10000

Asked by