Define d[i][j] to be the maximum number of floors that can be checked with i eggs after j steps.

To answer the query one should do the binary search to find number of steps X such that
 d[input_eggs][X] >= input_floors with X being smallest possible.

d[i][i] = i, d[2][5] = 15 ,d[2][6] = 21 ( 1 -> 6 -> 11 -> 15 -> 18 -> 20 -> 21 )

d[i][j] = d[i - 1][j] + d[i - 1][j - 1] + 1;

Explanation of the formula:

Suppose we know d[i][j - 1] and d[i - 1][j - 1]

Throw an egg from (d[i - 1][j - 1] + 1) floor. Did it break? If yes, we can definitely check all floors from the first to d[i - 1][j - 1]th with remaining i - 1 eggs within remaining j - 1 steps. If it didn't then you just check how many floors you can check at most with i eggs within j - 1 steps starting from ((d[i - 1][j - 1] + 1) + 1) th floor

d[i][j] can be calculated in N^2
Query is answered in log(N) time

My Java 1.8 solution runs in 0.062s.

Edited by author 19.03.2018 20:45