网站页面
当前课程
成员
General
主题 1
主题 2
主题 4
主题 5
主题 6
主题 7
主题 8
主题 9
主题 10
主题 11
主题 12
主题 13
主题 14
主题 15
主题 16
主题 17
主题 18
主题 19
主题 20
[URAL 1223]鹰蛋
成绩 | 开启时间 | 2014年09月19日 星期五 10:08 | |
折扣 | 0.8 | 折扣时间 | 2014年09月26日 星期五 10:08 |
允许迟交 | 是 | 关闭时间 | 2014年09月26日 星期五 10:08 |
输入文件 | eagleegg.in | 输出文件 | eagleegg.out |
【题目描述】
在很久,很久以前,有一只鹰在切尔诺贝利一栋大楼的房顶上筑了一个巢。随着时间的推移,巢里面出现了一些鹰蛋。在阳光明媚的一天,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 10 2 5 0 0
【样例输出】
10 3
【提示】
下面用T表示数据组数,N表示楼层数,M表示鹰蛋数。
对于30%的数据,1<=T<=10,1<=N<=100
对于50%的数据,1<=T<=10,1<=N<=1000
对于70%的数据,1<=T<=100,1<=N<=1000
对于100%的数据,1<=T<=1000,1<=N<=1000,1<=M<=1000