# UVa 10934

## Summary

Given $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 $N$ floors from which you can drop a balloon so that it bursts.

## Explanation

Dynamic programming works well here. But since $N$ is VERY big, a direct formulation of the problem statement will not work. Instead, you may consider a related question: given $k$ ($\leq 100$ ) balloons and $T$ ($\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 $N$ floors with $k$ balloons and $T$ trials, then we can handle shorter buildings with $\leq k$ balloons and $\leq T$ trials. (Why?)

It is obvious to see the optimal strategy: in a tall building, if you have $k$ balloons and $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 $k-1$ balloons and $T-1$ trials is maximized.

## Input

1 40
2 9223372036854775807
63 9223372036854775807
0 0


## Output

40
More than 63 trials needed.
63