427. Fewest Drops to Find the Floor
A building has f floors. There is a floor t such that an egg dropped from
floor t or above breaks, and one dropped below t does not. You have e eggs;
a broken egg is gone, an unbroken one may be reused.
Print the FEWEST drops that are guaranteed to determine t in the worst case.
The phrase "in the worst case" is the whole problem. This is not a question about averages or about luck: the answer must hold however the breaks fall, so every drop is evaluated by its WORSE outcome.
With one egg there is no choice. Dropping it anywhere but the lowest untested
floor risks losing the egg with floors still unknown, so the only safe strategy is
to climb one floor at a time, and the answer is f.
With more eggs, a drop from floor x splits the problem:
it breaks -> one fewer egg, and x - 1 floors below to search
it survives -> same eggs, and f - x floors above to search
so the cost of choosing x is 1 + max( those two ), and the answer is the
minimum over x:
dp[e][f] = min over x in 1..f of 1 + max( dp[e-1][x-1], dp[e][f-x] )
max because the adversary picks the worse branch, min because you pick the
floor. Getting those two the wrong way round is the classic error and produces a
much smaller, meaningless number.
Note dp[e][0] = 0: with no floors there is nothing to determine.
Constraints - `1 ≤ e ≤ 10` - `0 ≤ f ≤ 200`
Input
One line containing two integers e and f.
Output
Print the fewest drops guaranteed to determine the critical floor.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.