UVa 10934

From Algorithmist
Jump to navigation Jump to search

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