1509. [Ural 1223] 鹰蛋

【题目描述】

在很久，很久以前，有一只鹰在切尔诺贝利一栋大楼的房顶上筑了一个巢。随着时间的推移，巢里面出现了一些鹰蛋。在阳光明媚的一天，$Niels$ $Bohr$（提出哥本哈根解释的那个$Niels$ $Bohr$——译者注）正在房顶上散步。他突然说：“哦！显然所有鹰蛋都有相同的坚硬程度，因此一定有一个非负整数 $E$，如果将鹰蛋从第 $E$ 层（及其下面的所有层）摔下，它不会碎，但从第 $E+1$ 层（及其上面的所有层）摔下就碎了。”$Bohr$ 教授将要进行一系列实验（也就是摔鹰蛋）。实验的目的是确定 $E$ 的值。显然可以通过从最底层开始，由低到高依次摔鹰蛋来寻找 $E$。但还有别的方法可以用更少的实验次数来确定 $E$。你将要找出在最坏情况下为了确定 $E$ 而摔鹰蛋的最小次数。注意，摔下去但没有碎的鹰蛋可以在之后的实验中重新使用，但摔碎的鹰蛋就不能使用了。你求出的实验次数必须确保鹰蛋不会在找到 $E$ 的值之前全部摔碎。

楼层以从 $1$ 开始的正整数编号。如果一个鹰蛋从 $1$ 楼摔下去就碎了，你应该认为 $E=0$。如果 $E$ 从顶层摔下去仍然没有碎，认为 $E$ 等于楼层数。

【输入格式】

输入包含至多 $1000$ 组数据。

每组数据有 $1$ 行，包含 $2$ 个由空格分割的正整数：蛋的数量和楼层数。这两个数都不超过 $1000$.

输入结束标志为一行两个 $0$.

【输出格式】

对每组数据，输出一行，即最坏情况下最小的实验次数。

【样例1输入】

1 10
2 5
0 0

【样例1输出】

10
3

【样例2】

点击下载样例2

【数据规模】

下面用 $T$ 表示数据组数，$N$ 表示楼层数，$M$ 表示鹰蛋数。

对于 $30\%$ 的数据，$1 \leq T \leq 10,1 \leq N \leq 100$

对于 $50\%$ 的数据，$1 \leq T \leq 10,1 \leq N \leq 1000$

对于 $70\%$ 的数据，$1 \leq T \leq 100,1 \leq N \leq 1000$

对于 $100\%$ 的数据，$1 \leq T \leq 1000,1 \leq N \leq 1000，1 \leq M \leq 1000$

【来源】

URAL 1223 Chernobyl’ Eagle on a Roof