两枚鸡蛋

2 Eggs

专题: Strategy / 策略
难度: L2
来源: Brainstellar

题目详情

有一栋 100 层楼，存在一个临界楼层 $F$ ：

从高于 $F$ 的楼层扔鸡蛋会碎；
从不高于 $F$ 的楼层扔鸡蛋不会碎。

你有 2 枚鸡蛋，目标是在最坏情况下用尽量少的次数确定 $F$ 。

An Egg breaks only if dropped from above a threshold floor, within a 100-story building. Every time you drop an egg, it is counted as an attempt. You are given 2 eggs to deduce the threshold floor, with a minimum number of attempts in the worst case!

Hint

If we had only 1 egg, we would go linearly from 1 to 100. Having an extra egg allows for skipping some floors. When 1st egg breaks, the second egg can move linearly.

解析

最优最坏次数是 14 次。

思路：第一枚蛋采用递减步长试探：先在 14 楼扔，再加 13 到 27 楼，再加 12 到 39 楼……直到碎掉；第二枚蛋在上一次安全楼层与当前碎裂楼层之间线性查找。

之所以是 14：需要最小整数 $n$ 使

1+2+\cdots+n=\frac{n(n+1)}{2}\ge 100.

解得最小 $n=14$ （因为 $13\cdot14/2=91<100$ ， $14\cdot15/2=105\ge100$ ）。

Original Explanation

It can be done in 14 steps in the worst case.

Solution

We can skip some floors and jump ahead when testing with the first egg (egg1). Whenever egg1 breaks, egg2 has to scan linearly from the last safe floor to the floor where egg1 broke.

For example, we can test floors 10, 15, 20 and so on. Suppose egg1 broke at the $20^{\text{th}}$ floor, now we need to test from 16 to 19, which can be done one by one using the second egg (egg2). But this is suboptimal, because regardless of when egg1 breaks, egg2 is always taking 4 attempts. We can improve this algorithm by reducing the length of the gap on each attempt of egg1.

For instance, if we test at floor 10, 10+9, 10+9+8, and so on, then in the worst case, the number of attempts will be at-most (1+9)=10 or (2+8)=10 and so on... But, there's a problem, this sequence ends at $10+9+8... = n \cdot (n+1)/2 = 55$ and does not span the entire range of 100 floors. But the idea is in the right direction.

A solution for minimum steps in the worst case is the smallest integer greater than or equal to the positive solution of $x \cdot (x+1)/2=100 \implies x=13.651$

Start at floor 14, if the egg breaks start linearly from 1, if it does not break then drop the egg from $14+13 = 27^{\text{th}}$ floor, and so on. The following table can be constructed.

Egg1 Attempt	JumpSize	Egg1 Floor	Egg2 max attempts	Total Attempts
1	14	14	13	14
2	13	27	12	14
3	12	39	11	14
4	11	50	10	14
5	10	60	9	14
6	9	69	8	14
7	8	77	7	14
8	7	84	6	14
9	6	90	5	14
10	5	95	4	14
11	4	99	3	14
12	1	100	0	12

This ensures at-most 14 attempts.

Egg1 Attempt	JumpSize	Egg1 Floor	Egg2 max attempts	Total Attempts
1	14	14	13	14
2	13	27	12	14
3	12	39	11	14
4	11	50	10	14
5	10	60	9	14
6	9	69	8	14
7	8	77	7	14
8	7	84	6	14
9	6	90	5	14
10	5	95	4	14
11	4	99	3	14
12	1	100	0	12

Egg1 Attempt	JumpSize	Egg1 Floor	Egg2 max attempts	Total Attempts
1	14	14	13	14
2	13	27	12	14
3	12	39	11	14
4	11	50	10	14
5	10	60	9	14
6	9	69	8	14
7	8	77	7	14
8	7	84	6	14
9	6	90	5	14
10	5	95	4	14
11	4	99	3	14
12	1	100	0	12

Egg1 Attempt	JumpSize	Egg1 Floor	Egg2 max attempts	Total Attempts
1	14	14	13	14
2	13	27	12	14
3	12	39	11	14
4	11	50	10	14
5	10	60	9	14
6	9	69	8	14
7	8	77	7	14
8	7	84	6	14
9	6	90	5	14
10	5	95	4	14
11	4	99	3	14
12	1	100	0	12