We can only drop at most ~2 \times 10^5~ eggs, so each egg variety can be dropped at most ~\frac{2 \times 10^5}{10^4} = 20~ times on average. We therefore need to implement a variant of binary search. Simply binary searching for each egg variety individually is sufficient to score ~5\%~ of the points. In order to reduce the number of moves, we should use parallel binary search. The following two strategies are based around different methods of implementing parallel binary search:

Strategy 1: Divide and Conquer

Consider a function which takes in a contiguous range of floors ~[low, high]~ and a list of egg varieties corresponding to them in some order, and assigns each egg variety to a floor. Then:

• If there is only one floor, then the only egg variety must correspond to this floor.
• Otherwise, drop each egg variety from the floor ~mid = \lfloor \frac{low + high}{2} \rfloor~. The egg varieties that shattered must correspond to the floors ~[low, mid]~, whilst the remaining eggs must correspond to the floors ~[mid+1, high]~. We can recursively solve each half.

Naively implemented, this solution scores about ~23\%~ of the points. We can further apply the following optimizations:

• When solving for a group of egg varieties and a range of floors, if we've already found all egg varieties that will shatter, or all eggs that will not shatter, then we can short-circuit and avoid dropping the rest of the eggs since we can deduce whether they will shatter.
• We can choose the order in which we can recurse on each half in order to minimize the number of turn-arounds.
• We can choose any value of ~mid~ in the range ~[low, high)~, rather than exactly in the middle, sacrificing extra egg drops for fewer moves and turn-arounds. The optimal value of ~mid~ can be computed using dynamic programming. The exact details are left as an exercise to the reader.

A well implemented solution can score ~92\%~ of the points.

Strategy 2: Sweep

The previous strategy had the disadvantage that it required many turn-arounds. We should therefore look for an implementation of parallel binary search that doesn't require many direction changes:

• For each egg variety ~i~, we maintain variables ~low_i~ and ~high_i~, meaning that we know that the answer for this egg variety is in the range ~[low_i, high_i]~.
• Then, while there exists at least one egg variety with ~low_i \ne high_i~, we compute ~mid_i = \frac{low_i + high_i}{2}~ for each ~i~ where ~low_i \ne high_i~.
• We process the egg varieties by increasing order of ~mid_i~, dropping the ~i~-th egg variety at floor ~mid_i~. We can adjust the values of ~low_i~ and ~high_i~ as in a traditional binary search.

This strategy allows us to halve the range of every egg variety in a single sweep, without changing direction. Naively implemented, this solution scores about ~14\%~ of the points. We can further apply the following optimizations:

• In order to minimise movements and direction changes, we should alternate between processing egg varieties by increasing order of ~mid_i~ and decreasing order of ~mid_i~. This is already sufficient to score ~36\%~ of the points.
• We can apply the same short-circuiting optimization as in Strategy ~1~.
• Suppose we are processing the egg varieties by increasing order of ~mid_i~. If we ever set ~low_i = mid_i + 1~, we can recalculate ~mid_i~ and allow this egg variety to be processed in the same sweep. We can do something similar when processing the egg varieties by decreasing order of ~mid_i~.
• Once again, we can choose the value of ~mid_i~ to be anything in the range ~[low_i, high_i)~. The optimal value of ~mid_i~ can be computed using dynamic programming, although this is less straightforward; it helps to approximate the total number of moves as ~N \times (~number of sweeps~+ 1)~. The exact details are left as an exercise to the reader.

This strategy can score all ~100\%~ of the points.