Есть такая задачка

There is a building of 100 floors. If an egg drops from the Nth floor or above it will break.
If it’s dropped from any floor below, it will not break.
You’re given 2 eggs. Find N, while minimizing the number of drops for the worst case.

далее идет объяснение решения

Observation: Regardless of how we drop Egg1, Egg2 must do a linear search. i.e., if Egg1 breaks between floor 10 and 15, we have to check every floor in between with the Egg2
The Approach:
A First Try: Suppose we drop an egg from the 10th floor, then the 20th, …
»»If the first egg breaks on the first drop (Floor 10), then we have at most 10 drops total.
»»If the first egg breaks on the last drop (Floor 100), then we have at most 19 drops total (floors 10, 20, ... ,90, 100, then 91 through 99).
»»That’s pretty good, but all we’ve considered is the absolute worst case. We should do some “load balancing” to make those two cases more even.
Goal: Create a system for dropping Egg1 so that the most drops required is consistent, whether Egg1 breaks on the first drop or the last drop.
1. A perfectly load balanced system would be one in which Drops of Egg1 + Drops of Egg2 is always the same, regardless of where Egg1 broke.
2. For that to be the case, since each drop of Egg1 takes one more step, Egg2 is allowed one fewer step.
3. We must, therefore, reduce the number of steps potentially required by Egg2 by one drop each time. For example, if Egg1 is dropped on Floor 20 and then Floor 30, Egg2 is potentially required to take 9 steps. When we drop Egg1 again, we must reduce potential Egg2 steps to only 8. That is, we must drop Egg1 at floor 39.
4. We know, therefore, Egg1 must start at Floor X, then go up by X-1 floors, then X-2, …, until it gets to 100.
5. Solve for X+(X-1)+(X-2)+…+1 = 100. X(X+1)/2 = 100 -> X = 14
We go to Floor 14, then 27, then 39, … This takes 14 steps maximum.

Мне вот непонятно, а почему надо начинать с 14 этажа?
У нас два яйца только. Если с 14 кинули первое и оно разбилось, то ведь мы можем не найти N этаж.
В чем пойнт?

Спасибо!

Здравствуйте, e.thrash, Вы писали:

ET>Мне вот непонятно, а почему надо начинать с 14 этажа?

ET>У нас два яйца только. Если с 14 кинули первое и оно разбилось, то ведь мы можем не найти N этаж.

Почему? Кидаем второе начиная с 1-го этажа. В любом случае не более 14 попыток получается.

Здравствуйте, e.thrash, Вы писали:

ET>Мне вот непонятно, а почему надо начинать с 14 этажа?

5-й пункт не заметил?

Здравствуйте, wildwind, Вы писали:

W>Здравствуйте, e.thrash, Вы писали:

ET>>Мне вот непонятно, а почему надо начинать с 14 этажа?

W>5-й пункт не заметил?

Заметил, но не понял логику.
Не затруднит пояснить?

Здравствуйте, e.thrash, Вы писали:

ET>Есть такая задачка
Кстати, эта задачка легко обобщается на произвольное количество яиц. И когда-то уже была тут.

ET>У нас два яйца только. Если с 14 кинули первое и оно разбилось, то ведь мы можем не найти N этаж.
ET>В чем пойнт?

Идея в том, что первое яйцо мы кидаем с большим (постепенно уменьшающимся) шагом: F1 = 0+d0, F2 = F1+d1, F3 = F2+d2, ..., 100
Как только оно разбивается на шаге k, мы делаем вывод, что F[k-1] < N <= F[k]
И начинаем ронять второе яйцо, тоже в возрастающей последовательности, но уже с шагом 1: S1 = F[k-1]+1, S2 = S1+1, S3 = S2+1, ..., F[k] исключительно

Итого получается количество бросков
1 + 1..d0-1 — если первое яйцо разбилось с первой же попытки
2 + 1..d1-1 — если только со второй
3 + 1..d2-1 — если только с третьей
etc.

Нехитрым способом (отсчитывая от самого последнего этажа) находим, чему должны быть равны [d0,...,dm]

Здравствуйте, e.thrash, Вы писали:

ET>Есть такая задачка

ET>

ET>There is a building of 100 floors. If an egg drops from the Nth floor or above it will break.
ET>If it’s dropped from any floor below, it will not break.
ET>You’re given 2 eggs. Find N, while minimizing the number of drops for the worst case.

Вот тут:
https://www.facebook.com/notes/cracked-minds/throwing-eggs-from-a-building/1253975371280039
Есть ещё бонус:

Bonus: solve this for K eggs and N stories

Здравствуйте, Caracrist, Вы писали:

C>Bonus: solve this for K eggs and N stories

	Элементарно.
	Схема та же самая: первое яйцо поднимаем с большими шагами до самого верха, второе яйцо поднимаем с предпоследней до последней-1 попытки первого яйца, и т.д. Можно переиначить задачу, найти функцию N от K,T, где T — максимальное число попыток. N(1,T) = T. N(K,T) = N(K-1,T-1) + N(K-1,T-2) + ... + N(K-1,1) и понятно, что O(N) = O(T**K). N(2,T) = T*(T+1)/2 N(3,T) = T*(T+1)*(T+2)/6 N(K,T) = C(T+K-1,K) То есть, функция очень лихо растёт, поэтому найти корень T : N(K,T-1) < N <= N(K,T) бисекцией будет очень быстро. Решать тырнадцатеричные уравнения аналитически — необязательно.

UPD. спрятал ответ под кат, чтоб не спойлерить