Упс. Извиняюсь. Да, нельзя меньше, чем 14.
Вот толковое объяснение решения:
Если бы в наличии было всего одно яйцо, то пришлось бы последовательного сбрасывать его с первого этажа, потом со второго, и далее до сотого, но у нас их два, поэтому используем второе для минимизации количества тестов. Будем делить оставшееся количество этажей пополам, сначала сбросим яйцо с 50-го этажа, если разбилось, значит оставшееся яйцо надо будет последовательно сбрасывать с 1-го по 49й этаж, если не разбилось, то бросаем его снова, с 75-го этажа, и так далее. В худшем случае 50 тестов.
Это первое решение, которое пришло в голову так ищет информацию Rambler, тут коварный HR-менеджер предложит Вам улучшить своё решение, и не спешите спорить с ним на бутылку водки, что это решение и так самое лучшее.
Как Вы уже поняли, самая медленная часть в этом решении - это линейный поиск по одному этажу, поэтому надо найти оптимальное кличество отрезков, на которое надо разделить здание, чтобы сократить поиск, используя второе яйцо.
Пусть X будет необходимое количество попыток. Таким образом, если одно яйцо разобьется, то оставшееся надо будет бросить X-1 раз. Если яйцо не разбилось, то на следующем этапе (если оно разобьется) на тесты с оставшимся яйцом останется X-2 попыток. Объясню на примере - Мы решили что оптимальное количество попыток всего 16, тогда бросаем одно яйцо с шестнадцатого этажа (уже одна израсходованная попытка), и если оно разбилось, то с помощью оставшегося проверяем 16-1=15 этажей. Если оно не разбилось, то у нас осталось в запасе 15 попыток, значит на следующем этапе нужно будет бросать яйцо (и еще одна попытка будет использована) с 16+15+1=32 этажа, так как если яйцо разобьется на 32м этаже, нам хватит 14 попыток чтобы проверить этажи с 17 по 31й.
Нам нужно найти, какое количество опытов будет оптимальным, это будет такое количество, при котором на заключительном этапе понадобится 0 экспериментов. Запишем это в виде последовательности:
(1+a) + (1+(a-1))+ (1+(a-2)) + ...+ (1+0) >= 100
Где 1+p это и будет то количество опытов, которое мы ищем, обозначим его X. Тогда X(X+1)/2 >=100 в нашем случае, надеюсь, Вы не забыли как решать квадратные уравнения?
На случай, если забыли, ответ будет 14, соответственно одним яйцом (если оно не разбивается) будем проверять 14й, 27й, 39й, 50й, 60й, 69й, 77й, 84й, 90й, 95й, 99й, 100й этажи, если на одном из этапов яйцо разобьется, то проверим этажи, от максимального, где яйцо еще не билось, до того где оно разбилось.
Получаем результат - до 14 тестов.
Если бы в здании было 36 этажей, тогда X(X+1)/2>=36, решение было бы X=8, и проверить нужно будет 8, 15, 21, 26, 30, 33, 35, 36 этажи, пока яйцо не разобьется.
