'''
标准版面试题
[题目描述]
假设有个100层高的建筑，如果一个鸡蛋从N层或者高于N层坠落，会摔破。
如果鸡蛋从任何低于N层的楼层坠落，则不会破。
现在给你2个鸡蛋，设计方案找出N，并且保证在最坏情况下， 最小化鸡蛋下落的次数。
(假设每次摔落时，如果没有摔碎，则不会给鸡蛋带来损耗)

[Method 0]: 二分法。
先用第一个鸡蛋从第50层摔，再第25层......
不可行，因为如果第50层碎了，则N在第1~50层，
此时只能从1开始1层层地试到第49层（不能直接先到第25层摔，因为如果碎了，此时已经碎了2个鸡蛋，没有多余的鸡蛋摔），
所以最坏情况需要50次。


[Method 1]:将100层楼分成10分，每一份就是10层楼。
首先，将鸡蛋从第10层楼开始扔。那么结果有两种可能：

情况1：如果碎了，说明临界楼层在1到10之间，但现在只剩下一个鸡蛋了，只能从第一层一直到第10层。
情况2：如果没有碎，接下来从第20层扔鸡蛋。

该方法的思路是，用一个鸡蛋来试探，找到临界楼层的大致范围[1~10]、[11-20]….[91-100]。
然后用另一个鸡蛋在大致范围内找出精确楼层。

[Worst Case]：摔18次。
即从第10楼到第90楼鸡蛋都未碎，则N肯定在91~100之间，此时已经试了9次；
接着从91开始1层层地摔，直到第99层都未碎，则N必为100，此时已经摔了9次。
总共摔9+9 = 18次。

并不高效。


[Method 2]:
我们先假设最坏情况下，鸡蛋下落次数为x，即我们为了找出N，一共用鸡蛋做了x次的实验。
那么，我们第一次应该在哪层楼往下扔鸡蛋呢？先让我们假设第一次是在第y层楼扔的鸡蛋，
如果第一个鸡蛋在第一次扔就碎了，我们就只剩下一个鸡蛋，要用它准确地找出N，
只能从第一层向上，一层一层的往上测试，直到它摔坏为止，答案就出来了。
 由于第一个鸡蛋在第y层就摔破了， 所以最坏的情况是第二个鸡蛋要把第1到第y-1层的楼都测试一遍，
 最后得出结果， 噢，原来鸡蛋在第y-1层才能摔破(或是在第y-1层仍没摔破，答案就是第y层。)
 这样一来测试次数是1+(y-1)=x，即第一次测试要在第x层。

如果第一次测试鸡蛋没摔破呢？假设第二次从y层开始摔，则 x < y < 100,
同理，如果第二次用第一个鸡蛋在y层摔碎了找到了区间，则用第二个鸡蛋进一步找，
则最坏情况需要从第x+1层试到第y-1层，一共是摔y-1-(x-1)+1次，
而此时第二个鸡蛋还剩x-2次可以摔，所以 y-1-(x-1)+1 = x-2，得 y = 2x-1,即 y = x + x-1，
所以第二次摔的层数比第一次的x层高x-1层。
同理可得第三次摔的层数为x + x-1 + x-2,
然后 x + x-1 + x-2 + x-3 + ...，因此有：
x + x-1 + x-2 + x-3 + ... + 1 = 100
即 (x+1)*x/2 = 100, 求得 x=14（因为14^2=196 < sqr(200)）。

即我先用第1个鸡蛋在以下序列表示的楼层数不断地向上测试，直到它摔破。
再用第2个鸡蛋从上一个没摔破的序列数的下一层开始，向上测试， 即可保证在最坏情况下也只需要测试14次，
就能用2个鸡蛋找出从哪一层开始， 往下扔鸡蛋，鸡蛋就会摔破。

14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99, 100

比如，我第1个鸡蛋是在第77层摔破的，那么我第2个鸡蛋就从第70层开始，向上测试，
第二个鸡蛋最多只需要测试7次(70,71,72,73,74,75,76)，加上第1个鸡蛋测试的 7次(14,27,39,50,60,69,77)，
最坏情况只需要测试14次即可得出答案。

'''

df447736c472db263e2b45ebc93463fc3c8903a6
<mask token>

'''
标准版面试题
[题目描述]
假设有个100层高的建筑，如果一个鸡蛋从N层或者高于N层坠落，会摔破。
如果鸡蛋从任何低于N层的楼层坠落，则不会破。
现在给你2个鸡蛋，设计方案找出N，并且保证在最坏情况下， 最小化鸡蛋下落的次数。
(假设每次摔落时，如果没有摔碎，则不会给鸡蛋带来损耗)

[Method 0]: 二分法。
先用第一个鸡蛋从第50层摔，再第25层......
不可行，因为如果第50层碎了，则N在第1~50层，
此时只能从1开始1层层地试到第49层（不能直接先到第25层摔，因为如果碎了，此时已经碎了2个鸡蛋，没有多余的鸡蛋摔），
所以最坏情况需要50次。


[Method 1]:将100层楼分成10分，每一份就是10层楼。
首先，将鸡蛋从第10层楼开始扔。那么结果有两种可能：

情况1：如果碎了，说明临界楼层在1到10之间，但现在只剩下一个鸡蛋了，只能从第一层一直到第10层。
情况2：如果没有碎，接下来从第20层扔鸡蛋。

该方法的思路是，用一个鸡蛋来试探，找到临界楼层的大致范围[1~10]、[11-20]….[91-100]。
然后用另一个鸡蛋在大致范围内找出精确楼层。

[Worst Case]：摔18次。
即从第10楼到第90楼鸡蛋都未碎，则N肯定在91~100之间，此时已经试了9次；
接着从91开始1层层地摔，直到第99层都未碎，则N必为100，此时已经摔了9次。
总共摔9+9 = 18次。

并不高效。


[Method 2]:
我们先假设最坏情况下，鸡蛋下落次数为x，即我们为了找出N，一共用鸡蛋做了x次的实验。
那么，我们第一次应该在哪层楼往下扔鸡蛋呢？先让我们假设第一次是在第y层楼扔的鸡蛋，
如果第一个鸡蛋在第一次扔就碎了，我们就只剩下一个鸡蛋，要用它准确地找出N，
只能从第一层向上，一层一层的往上测试，直到它摔坏为止，答案就出来了。
 由于第一个鸡蛋在第y层就摔破了， 所以最坏的情况是第二个鸡蛋要把第1到第y-1层的楼都测试一遍，
 最后得出结果， 噢，原来鸡蛋在第y-1层才能摔破(或是在第y-1层仍没摔破，答案就是第y层。)
 这样一来测试次数是1+(y-1)=x，即第一次测试要在第x层。

如果第一次测试鸡蛋没摔破呢？假设第二次从y层开始摔，则 x < y < 100,
同理，如果第二次用第一个鸡蛋在y层摔碎了找到了区间，则用第二个鸡蛋进一步找，
则最坏情况需要从第x+1层试到第y-1层，一共是摔y-1-(x-1)+1次，
而此时第二个鸡蛋还剩x-2次可以摔，所以 y-1-(x-1)+1 = x-2，得 y = 2x-1,即 y = x + x-1，
所以第二次摔的层数比第一次的x层高x-1层。
同理可得第三次摔的层数为x + x-1 + x-2,
然后 x + x-1 + x-2 + x-3 + ...，因此有：
x + x-1 + x-2 + x-3 + ... + 1 = 100
即 (x+1)*x/2 = 100, 求得 x=14（因为14^2=196 < sqr(200)）。

即我先用第1个鸡蛋在以下序列表示的楼层数不断地向上测试，直到它摔破。
再用第2个鸡蛋从上一个没摔破的序列数的下一层开始，向上测试， 即可保证在最坏情况下也只需要测试14次，
就能用2个鸡蛋找出从哪一层开始， 往下扔鸡蛋，鸡蛋就会摔破。

14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99, 100

比如，我第1个鸡蛋是在第77层摔破的，那么我第2个鸡蛋就从第70层开始，向上测试，
第二个鸡蛋最多只需要测试7次(70,71,72,73,74,75,76)，加上第1个鸡蛋测试的 7次(14,27,39,50,60,69,77)，
最坏情况只需要测试14次即可得出答案。

'''
