当前位置:网站首页>Lesson 1: hardness of eggs
Lesson 1: hardness of eggs
2022-07-07 09:32:00 【Fight! Sao Nian!】
subject :AcWing 1048. The hardness of the egg
lately XX The company held a strange competition : The king of egg hardness competition .
The contestants are hens from all over the world , The content of the competition is to see who lays the hardest egg , What's more strange is that XX The company does not use any precision instruments to measure the hardness of eggs , They adopted the most old-fashioned method – Throw eggs from height – To test the hardness of eggs , If a hen lays an egg from the top of a tall building a The layer fell without breaking , But from a+1 The floor broke when it fell , Then say that the hardness of this hen's egg is a.
Of course, you can find various reasons to explain that this method is unscientific , For example, the hardness of the eggs laid by the same hen may be different, and so on , But it doesn't affect XX The competition of the company , Because they just want to attract everyone's attention , Eggs come from 100 When falling from a high building on the first floor , This scene can still attract many people to stop and watch , Of course ,XX The company will never forget to hang a banner on the tall building , write “XX company ” The words... – This game is just XX An alternative advertisement of the company .
Diligent little A You can always find a mathematical problem in one thing , This is no exception .
“ If there are many eggs with the same hardness , Then I can use the method of two points to measure the hardness of the egg with the least number of times ”, Small A I am very satisfied with my conclusion , But soon trouble came ,“ however , What if I don't have enough eggs , For example, I only have 1 An egg , Then I have to start from 1 Throw it from floor to floor , At worst, I will throw 100 Time . If there is 2 An egg , Then from 2 Throw it at the beginning of the first floor …… wait , incorrect , It seems that we should start from 1/3 It's the right place to start throwing , Um. , I don't think so ……3 What about an egg ,4 individual ,5 individual , More ……”, As usual , Small A Another thinking impasse , He is not so much diligent in thinking , Rather, he likes to ask for trouble .
ok , Now that the trouble has come , Someone has to solve it , Small A It's up to you to solve the problem .
Input format
Input includes multiple sets of data , One line for each group of data , Contains two positive integers n and m, among n Indicates the height of the building ,m It means the number of eggs you have now , These eggs have the same hardness ( That is, when they fall from the same height, they either break or don't break ), And less than or equal to n.
You can assume that the hardness is x The height of eggs is less than or equal to x The place where you fall will not break anyway ( Unbroken eggs can be used ), As long as we compare x If you throw it high, it will break .
Enter data for each group , You can assume that the hardness of the egg is 0 to n Between , That is to say n+1 Throwing eggs in layers will surely break .
Output format
For each set of inputs , Output an integer , Indicates the number of egg throwing times required in the worst case using the optimal strategy .
Data range
1≤n≤100,
1≤m≤10
sample input :
100 1
100 2
sample output :
100
14
Sample explanation
The optimal strategy refers to the strategy that needs the least egg throwing times in the worst case .
If there is only one egg , You can only throw it from the first floor , In the worst case , The hardness of an egg is 100, So you need to throw 100 Time . If other strategies are adopted , You may not be able to measure the hardness of an egg ( For example, you throw it on the second floor for the first time , It broke , At this time, you cannot be sure that the hardness is 0 still 1), That is, in the worst case, you need to throw unlimited times , So the answer to the first set of data is 100.
Topic analysis :
Because this problem is more complex, it will be continued ...
Here's an explanation 100 floor ,2 An egg only needs 14 How did the second come
We can use the answer 14 infer
If we stand for the first time 14 floor , If it is broken, we still need to judge 1~13 Lou Gong 13 Time , So add the first egg altogether 1+13=14 Time ;
If we stand here for the second time 14+13 floor , If it is broken, we still need to judge 15~26 common 12 Time , So add the first time and the second time 1+1+12=14 Time .
By analogy, we can know that we can definitely reach 100 layer .
边栏推荐
- In fact, it's very simple. It teaches you to easily realize the cool data visualization big screen
- Create an int type array with a length of 6. The values of the array elements are required to be between 1-30 and are assigned randomly. At the same time, the values of the required elements are diffe
- [4G/5G/6G专题基础-147]: 6G总体愿景与潜在关键技术白皮书解读-2-6G发展的宏观驱动力
- Unity shader (data type in cghlsl)
- Leetcode daily questions (2316. count unreachable pairs of nodes in an undirected graph)
- Variable parameter of variable length function
- Serializer & modelserializer of DRF serialization and deserialization
- esp8266使用TF卡并读写数据(基于arduino)
- Implementation of corner badge of Youmeng message push
- Binary tree high frequency question type
猜你喜欢
Dynamics 365online applicationuser creation method change
十二、排序
MySQL common statements
Sublime Text4 download the view in bower and set the shortcut key
Loxodonframework quick start
印象笔记终于支持默认markdown预览模式
JMeter JDBC batch references data as input parameters (the simplest method for the whole website)
Postman interface debugging method
软件建模与分析
網易雲微信小程序
随机推荐
Mysql数据库-锁-学习笔记
Postman data driven
Pytest+request+allure+excel interface automatic construction from 0 to 1 [five nails / flying Book notice]
Cesium load vector data
How to use clipboard JS library implements copy and cut function
Oracle installation enhancements error
如何成为一名高级数字 IC 设计工程师(1-6)Verilog 编码语法篇:经典数字 IC 设计
Unity shader (to achieve a simple material effect with adjustable color attributes only)
信息安全实验四:Ip包监视程序实现
Niuke - Huawei question bank (61~70)
Mysql database index study notes
asp. How to call vb DLL function in net project
【SVN】SVN是什么?怎么使用?
Unittest simple project
SiteMesh getting started example
沙龙预告|GameFi 领域的瓶颈和解决方案
Dynamics 365Online ApplicationUser创建方式变更
4、 Fundamentals of machine learning
Upload taro pictures to Base64
MySQL common statements