Skills101
← All coding problems

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).

Loading editor…

Log in to run and submit your code — it's free.