Если испытывать поочерёдно этажи 1, 2, 4, 8, ..., 2^K, 2^{K+1} до тех пор, пока яйцо не разобъётся, а потом уточнить значение F из промежутка 2^K..2^{K+1} бинарным поиском, количество попыток будет (2 lgF). Если слово «примерно» допускает коэффициент 2, то алгоритм подходит.
Если в распоряжении только одно яйцо, то нет никакого другого способа, кроме как идти снизу вверх подряд, O(N).
Если есть два яйца, первым можно идти с более грубым шагом A[1], A[2], A[3], ..., A[K], A[K+1], а вторым уточнять точное значение F из A[K]..A[K+1]. Причём шаг A[K+1]-A[K] определяет количество попыток для второго яйца, то есть суммарное количество попыток будет K+A[K+1]-A[K]. Осталось определить вид последовательности A[i], чтобы K+A[K+1]-A[K]=O(√A[K+1]).
Собственно, чтобы достичь 2(√N), нужно первым яйцом идти с шагом (√N), то есть 1, 1+(√N), 1+2(√N), 1+3(√N), ..., а когда разобъётся на 1+(K+1)(√N), идти вторым подряд с этажа 2+K(√N).
Простой
