Как выбросить 2 яйца из здания и найти пол F с ~ c * sqrt (F) бросает?

Question

Я читаю алгоритмы Седжвик 4-е издание книги, и он имеет следующую задачу:

Suppose that you have an N-story building and 2 eggs. Suppose also that an egg 
is broken if it is thrown off floor F or higher, and unbroken otherwise. Your 
cost model is the number of throws. Devise a strategy to determine F such that 
the number of throws ~c √ F for some constant c. 

Первая часть задачи является найти F в 2 √ N шагов, и вот решение для этого:

Solution to Part 1: To achieve 2 * sqrt(N), drop eggs at floors sqrt(N), 2 * 
sqrt(N), 3 * sqrt(N), ..., sqrt(N) * sqrt(N). (For simplicity, we assume 
here that sqrt(N) is an integer.) Let assume that the egg broke at level k * 
sqrt(N). With the second egg you should then perform a linear search in the 
interval (k-1) * sqrt(N) to k * sqrt(N). In total you will be able to find 
the floor F in at most 2 * sqrt(N) trials. 

Он также дает подсказку для ~ с √ F часть (часть 2):

Hint for Part 2: 1 + 2 + 3 + ... k ~ 1/2 k^2. 

Так что алгоритм, чтобы сделать это в ~ с шагом √ F?

Answer 1

Отбросьте первое яйцо с этажей 1, 3, 6, ... (частичные суммы 1, 2, 3, ...). Затем выполните линейный поиск между двумя последними этажами.