Jzj要来做一个经典的实验:测试鸡蛋壳的坚硬程度。
Jzj正好处于N层高的摩天大楼中,所以通过从某一楼层向下扔鸡蛋来测试鸡蛋壳的坚硬程度。
Jzj有M个鸡蛋,所有的鸡蛋硬度都一样。如果鸡蛋从第L层摔下去没有碎,而在L + 1层摔碎了,那么称鸡蛋的硬度是L。嗯,反正jzj不喜欢吃鸡蛋,所以不用担心浪费的问题。大楼共有N层高,如果在N层还没有摔碎,就认为硬度是N;如果在第1层就碎了,硬度为0。
虽然jzj不喜欢吃鸡蛋,但是jzj的好朋友yk特别喜欢吃鸡蛋。为了帮好朋友保护可怜的小鸡蛋,jzj想知道用这么多鸡蛋,最少摔几次就可以保证测试出它们的硬度。
【输入格式】
一行两个正整数,用空格隔开,没有多余字符。分别是M和N。
【输出格式】
输出最少次数。
【样例】
eggs.in
1 10
eggs.out
10
样例解释
由于只有一个鸡蛋,所以只好一层层试。鸡蛋一旦摔碎,就不能再使用了。
【数据规模】
30%的数据N<=100;
100%的数据N<= 1,000。还有:
1:一个魔术,可以把一个东西变少或者变多。但是变多或变少的模式只有三种。
(1) 变少一个
(2) 变多一个
(3) 变为原来的p次幂(p为任意正整数)。
求至少需要施展几次魔法能够把1根薯条变为n根。
输入一行一个正整数N,表示还能吃N根薯条。
输出一行一个整数,表示最少施展的魔法次数。
数据满足 1≤N≤1000000
2:有N块长度相同的长条木板,把每块木板分成了N个小单元,在这N*N个小单元上选了一些涂成了黑色。不过这样涂完了以后,发现把这N块小木板摆在一起太丑了,请交换其中的一些木板,把这些木板排的漂亮一点。
怎么排才漂亮呢?让所有的黑色小单元都尽量聚集在一起,也就是在以(1,1)(2,2)……(N,N)这条对角线以下的三角形区域里(可以包含对角线)。
要用最少的次数将原来的N个木板排成满足要求的样子,每一次操作可以交换任意两个相邻的木板。
输入第一行一个正整数N,表示木板数量。
下面N行,每行N个数0或1。0表示白色,1表示黑色。
输出一行一个整数,表示最少的操作次数是原图像变为漂亮图像。
数据满足 1≤N≤1000
|
|