# UVa 10934

## 10934 - Dropping Water Balloons[edit]

## Summary[edit]

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

## Explanation[edit]

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

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

## Input[edit]

1 40 2 9223372036854775807 63 9223372036854775807 0 0

## Output[edit]

40 More than 63 trials needed. 63