The lions of the jungle have long wished to ascend into the treetops, but as everybody knows, lions cannot climb. Their solution is to create a "lion ladder": The lions will stack themselves on top of one another until they reach the canopy. However, they are running into a big problem: Each lion can only support the weight of
other lions. Determine how many lions are required to reach a tree
lions tall!
Note: The output may be too large to fit inside a 32-bit integer. Use a 64-bit data type, such as long
in Java or long long
in C/C++.
Limitations
Subtask 1 (30%)
.
Subtask 2 (70%)
.
Input Specification
The only line of input will consist of two integers, and
.
Output Specification
Output one integer, representing the minimum number of lions required for the ladder.
Sample Input
2 5
Sample Output
8
Explanation
If one lion is at the peak (height 5), then there is at least one lion supporting that lion at height 4. One lion at height 3 can support both lions, but two lions are required to support the 3 lions above height 2. This makes 5 lions in total for the bottom layer to support, requiring 3 lions. Adding all the lions together, 8 lions are required for the whole ladder.
Comments