10934 - Dropping Water Balloons
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.
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.
1 40 2 9223372036854775807 63 9223372036854775807 0 0
40 More than 63 trials needed. 63