Egg Dropping
hardDynamic Programming II+40 XPTime limit 2s
A building has n floors. There is an unknown floor X (0 ≤ X ≤ n): an egg dropped from floor X or below survives, and an egg dropped from above X breaks. You have k identical eggs; a broken egg can't be reused, a surviving one can. In the worst case, what is the minimum number of drops needed to find X for sure?
Input: one line k n.
Output: the minimum number of drops.
Constraints: 1 ≤ k ≤ 100, 1 ≤ n ≤ 10⁹.
Examples: with 1 egg you must try floors 1, 2, 3, … in order, so n drops. With 2 eggs and 100 floors the answer is 14.
Think about it: the classic table drops[k][n] = 1 + min over x of max(drops[k−1][x−1], drops[k][n−x]) is far too slow for n = 10⁹. Flip the question: with m drops and k eggs, how many floors can you cover? cover(m, k) = cover(m−1, k−1) + cover(m−1, k) + 1 (the drop's floor, the floors below if it breaks, the floors above if it survives). Increase m until cover(m, k) ≥ n. Treat k = 1 separately (answer n).
Sample input 1
2 100
Sample output 1
14
Sample input 2
1 7
Sample output 2
7
Sample input 3
2 6
Sample output 3
3
Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).