ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

USU Championship 2002

About     Problems     Submit solution     Judge status     Standings
Contest is over

H. Chernobyl’ Eagle on a Roof

Time limit: 1.0 second
Memory limit: 64 MB
Once upon a time an Eagle made a nest on the roof of a very large building. Time went by and some eggs appeared in the nest. There was a sunny day, and Niels Bohr was walking on the roof. He suddenly said: “Oops! All eggs surely have the same solidity, thus there is such non-negative number E that if one drops an egg from the floor number E, it will not be broken (and so for all the floors below the E-th), but if one drops it from the floor number E+1, the egg will be broken (and the same for every floor higher, than the E-th).” Now Professor Bohr is going to organize a series of experiments (i.e. drops). The goal of the experiments is to determine the constant E. It is evident that number E may be found by dropping eggs sequentially floor by floor from the lowest one. But there are other strategies to find E for sure with much less amount of experiments. You are to find the least number of eggs droppings, which is sufficient to find number E for sure, even in the worst case. Note that dropped eggs that are not broken can be used again in following experiments.
The floors are numbered with positive integers starting from 1. If an egg has been broken being dropped from the first floor, you should consider that E is equal to zero. If an egg hasn’t been broken even being dropped from the highest floor, consider that E is also determined and equal to the total number of floors.


Input contains multiple (up to 1000) test cases. Each line is a test case. Each test case consists of two numbers separated with a space: the number of eggs, and the number of floors. Both numbers are positive and do not exceed 1000. Tests will end with the line containing two zeroes.


For each test case output in a separate line the minimal number of experiments, which Niels Bohr will have to make even in the worst case.


1 10
2 5
0 0
Problem Author: folklore, proposed by Alexander Klepinin, text by Nikita Shamgunov
Problem Source: The Seventh Ural State University collegiate programming contest
To submit the solution for this problem go to the Problem set: 1223. Chernobyl’ Eagle on a Roof