Problem
The skyscraper has n floors. It is known that if you drop a glass ball from floor number p and the ball breaks, then if you drop a ball from floor number p+1, it will also break. It is also known that when thrown from the last floor, the ball always breaks.
You want to define the minimum floor number that will cause the ball to break when it falls. For experiments, you have two balls. You can split them all, but you must be absolutely certain of that number in the end result.
Determine how many throws are enough to solve this problem.
Input
The program receives as input the number of floors in the skyscraper n.
Output
It is required to print the smallest number of throws, at which it is always possible to solve the problem.
Note
Comment to the first example. You need to throw the ball from the 2nd floor. If it breaks, then we will throw the second ball from the 1st floor, and if it does not break, then we will throw the ball from the 3rd floor.
Hints
1. What should you do if there is only one ball?
2. Let there be two balls and we have thrown one ball from floor number k. How will we act depending on whether the ball breaks or not?
3. Let
f(n) be the minimum number of throws required to determine the desired floor if the skyscraper had
n floors. Express
f(n) in terms of
f(a) values for smaller
a.
values
Examples
| # |
Input |
Output |
| 1 |
4 |
2 |
| 2 |
7 |
3 |
Запрещенные операторы: for; while; until