普及-⏱ 1000ms💾 256MB#P3175🏷️ 动态规划

题目描述

质检中心用一栋 $n$ 层的测试塔给玻璃球定抗摔等级:若玻璃球从第 $a$ 层摔下不碎、 从第 $a+1$ 层摔下必碎,则等级记为 $a$(等级为 $0$ 表示从第 1 层摔下即碎;同批玻璃球等级相同, 没摔碎的可以继续用)。

现在有 $m$ 颗玻璃球。测试次数越少越省成本,但必须保证在最坏情况下也能定出等级。 求使用最优策略时,最坏情况下需要的最少测试次数。

输入格式

多组数据,每组一行两个正整数 $n$ 和 $m$($1 \le n \le 100$,$1 \le m \le 10$), 分别表示塔的层数与玻璃球个数。

输出格式

每组数据输出一行一个整数:最坏情况下最少测试次数。

数据范围

$$1 \le n \le 100,\quad 1 \le m \le 10$$

样例输入 #1
100 1
100 2
样例输出 #1
100
14
样例输入 #2
100 10
50 3
10 5
样例输出 #2
7
7
4