比赛场次 | 623 |
---|---|
比赛名称 | 2024暑假C班集训D |
比赛状态 | 已结束比赛成绩 |
开始时间 | 2024-07-13 08:00:00 |
结束时间 | 2024-07-13 12:00:00 |
开放分组 | 全部用户 |
注释介绍 | dp专场,题目难度自行判断 |
题目名称 | 鹰蛋 |
---|---|
输入输出 | eagleegg.in/out |
时间限制 | 1000 ms (1 s) |
内存限制 | 256 MiB |
测试点数 | 10 简单对比 |
用户 | 结果 | 时间 | 内存 | 得分 |
---|---|---|---|---|
wdsjl | AAAAAAAAAA | 0.089 s | 6.59 MiB | 100 |
┭┮﹏┭┮ | AAAAAAAAAA | 0.142 s | 3.66 MiB | 100 |
qyd | AAAAAAAAAA | 0.143 s | 7.25 MiB | 100 |
darkMoon | AAAAAAAAAA | 0.292 s | 11.07 MiB | 100 |
liuyiche | AAAAAAAAAA | 1.430 s | 7.28 MiB | 100 |
健康铀 | AAAAAAAAAA | 2.696 s | 11.22 MiB | 100 |
袁书杰 | WWWWWAWWWW | 0.044 s | 3.79 MiB | 10 |
AeeE5x | WWWWWWWWWW | 0.031 s | 3.35 MiB | 0 |
djyqjy | WWWWWWWWWW | 0.034 s | 3.57 MiB | 0 |
LikableP | WWWWWWWWWW | 0.045 s | 3.38 MiB | 0 |
wzh0425 | WWWWWWWWWW | 0.048 s | 3.34 MiB | 0 |
ht骨架 | WWWWWWWWWW | 0.048 s | 3.34 MiB | 0 |
李奇文 | RRRRRRRRRR | 2.148 s | 10.64 MiB | 0 |
彭欣越 | WWWWTTTTTT | 12.270 s | 3.25 MiB | 0 |
在很久,很久以前,有一只鹰在切尔诺贝利一栋大楼的房顶上筑了一个巢。随着时间的推移,巢里面出现了一些鹰蛋。在阳光明媚的一天,$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
点击下载样例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$