U243958 双蛋问题

"双蛋问题" 曾经是 $Google$ 的一道经典的面试题。由于其过于经典，$Google$ 公司现在已经不再用这个题来面试。 “双蛋问题” 的描述如下： 有一栋 $100$ 层的高楼，在所有的楼层中存在一个临界楼层 $f$ ，满足 $0 \le f \le n$ ，任何从 **高于** $f$ 的楼层落下的鸡蛋都 **会碎** ，从 $f$ 楼层或比它低的楼层落下的鸡蛋都 **不会碎** 。 现在你有两个鸡蛋，在 **确保能够找出临界楼层 $f$** 的前提下，你 **最少** 需要扔多少次鸡蛋？ 当然，如果鸡蛋在扔下之后没有碎，那么这个鸡蛋就可以 **重复使用** 。如果鸡蛋碎了，就不能再用了。 你可以这样理解这个问题： 假如 **只有一个鸡蛋** ，要如何确保找到临界楼层 $f$ ？显然，由于只有一个鸡蛋可用，所以这个鸡蛋一旦碎了，就没有鸡蛋可扔了。所以为了 **保证** 可以找出临界楼层，你 **只能从第一层起，一层一层的扔** 。如果在某一层鸡蛋碎了，那么临界楼层就是该层的下面一层。如果扔到最后都没碎，那么临界楼层就是第 $100$ 层。所以 **最坏情况** 下，你需要扔 $100$ 次才能找到临界楼层。 而现在你有两个鸡蛋，所以这个问题被称为 “双蛋问题” 。 现在你需要编程找出这个问题的 **通解** ，即你一共有 $k$ 个鸡蛋，$n$ 层楼，那么在保证可以找出临界楼层的前提下，你 **最少** 要扔多少次鸡蛋？

给你 $k$ 枚相同的鸡蛋，并可以使用一栋从第 $1$ 层到第 $n$ 层共有 $n$ 层楼的建筑。 已知存在楼层 $f$ ，满足 $0 \le f \le n$ ，任何从 **高于** $f$ 的楼层落下的鸡蛋都会碎，从 $f$ 楼层或比它低的楼层落下的鸡蛋都不会破。 每次操作，你可以取一枚没有碎的鸡蛋并把它从任一楼层 $x$ 扔下（满足 $1 \le x \le n$）。如果鸡蛋碎了，你就不能再次使用它。如果某枚鸡蛋扔下后没有摔碎，则可以在之后的操作中 **重复使用** 这枚鸡蛋。 请你计算并返回要确定 $f$ **确切的值** 的 **最小操作次数** 是多少？

一行两个整数 $k$ 和 $n$，表示鸡蛋的数量和楼的层数。

一行一个整数，表示要确定 $f$ **确切的值** 的 **最小操作次数** 。

**数据范围** - $1 \le k \le 100$ 。 - $1 \le n \le 20000$ 。 **样例四解释** 有 $2$ 个蛋，$100$ 层楼，假如第一个蛋碎了，只剩一个蛋，那么就只能一层一层的扔，才能确保找出临界楼层。所以第一个蛋应该用来 **尽量的缩小临界楼层的范围** 。 考虑这样一种扔法： 第一个蛋从 $10$ 层开始扔，如果蛋碎了，那么就用第二个蛋来试 $1-9$ 层。如果没碎，那么再从 $20$ 层开始扔，如果碎了，就用第二个蛋试 $11-19$ 层，如果没碎，再从 $30$ 层开始扔……直到 $100$ 层为止。 第一个蛋在 $10$ 层就碎了，那么第二个蛋需要扔 $9$ 次，加上第一个蛋的 $1$ 次，最多需要扔 $10$ 次。如果第一个蛋在 $20$ 层碎了，那么第二个蛋最多需要扔 $9$ 次，加上第一个蛋的 $2$ 次，共需要扔 $11$ 次……如果第一个蛋在 $100$ 层才碎，那么就一共需要扔 $10+9=19$ 次。这已经是最坏的情况了。 但是这种扔法并非最优，因为第二个蛋每次都最多需要扔 $9$ 次，而第一个蛋需要扔的次数却不确定。可以考虑一种优化：**第一个蛋每多扔一次，就让第二个蛋少扔一次**。 即第一个蛋在 $14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99, 100$ 层扔，那么第二个蛋最多需要扔的次数为 $13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 1$ 。那么最坏情况下，如果第一个蛋在 $14$ 层就碎了，那么第二个蛋需要扔 $13$ 次，加上第一个蛋的 $1$ 次，共 $14$ 次。 可以证明，$14$ 次就是在 **保证能够找出临界楼层 $f$ 的情况下最少需要扔的次数** 。