# UVa 10934

## Summary

Given ${\displaystyle k}$ balloons, find a way using no more than 63 trials (i.e. dropping of balloons), to determine the lowest floor of a building of ${\displaystyle N}$ floors from which you can drop a balloon so that it bursts.

## Explanation

Dynamic programming works well here. But since ${\displaystyle N}$ is VERY big, a direct formulation of the problem statement will not work. Instead, you may consider a related question: given ${\displaystyle k}$ (${\displaystyle \leq 100}$) balloons and ${\displaystyle T}$ (${\displaystyle \leq 63}$) trials, find the tallest building that the problem can still be solved. Also note that if we can solve the case for a building of ${\displaystyle N}$ floors with ${\displaystyle k}$ balloons and ${\displaystyle T}$ trials, then we can handle shorter buildings with ${\displaystyle \leq k}$ balloons and ${\displaystyle \leq T}$ trials. (Why?)

It is obvious to see the optimal strategy: in a tall building, if you have ${\displaystyle k}$ balloons and ${\displaystyle T}$ trials left, you would certainly drop a balloon from a certain floor such that if the balloon bursts, the number of floors that can be handled with your remaining ${\displaystyle k-1}$ balloons and ${\displaystyle T-1}$ trials is maximized.

## Input

1 40
2 9223372036854775807
63 9223372036854775807
0 0


## Output

40
More than 63 trials needed.
63