Problem Statement
PROBLEM STATEMENT You are given an N-story building and M identical glass balls. The balls possess the following properties: - if a ball breaks when dropped from the Kth floor, then each of the balls break when dropped from the Kth floor, or from a higher floor. - if a ball doesn't break when dropped from the Kth floor, then each of the balls doesn't break when dropped from the Kth floor, of from a lower floor. - if a ball breaks you can't reuse it. - if a ball doesn't break you can always find it and reuse it. Consider strategies to find the lowest floor from which all the balls would break or to determine that they won't break when dropped from all the floors of this building. A strategy is called optimal if it minimizes the number of drops in the worst case scenario. That is, the strategy is optimal if you can always determine the required floor in not more than X drops, and for any strategy that requires less than X drops there is a situation when you can't uniquely determine the required floor. Your task is, given the number of floors in the building and the number of glass balls you have, find the maximum (i.e. worst case) number of drops in an optimal strategy. DEFINITION Class: GlassBalls Method: strategy Parameters: int, int Returns: int Method signature (be sure your method is public): int strategy(int numFloors, int numBalls); TopCoder will ensure the validity of the inputs. Inputs are valid if all of the following criteria are met: - numFloors is between 1 and 5000000 inclusive - numBalls is between 1 and 40 inclusive EXAMPLES 1. numFloors = 129, numBalls = 1, return 129 2. numFloors = 100, numBalls = 2, return 14 3. numFloors = 1000, numBalls = 2, return 45 4. numFloors = 567, numBalls = 4, return 12
Definition
- Class:
- GlassBalls
- Method:
- strategy
- Parameters:
- int, int
- Returns:
- int
- Method signature:
- int strategy(int param0, int param1)
- (be sure your method is public)
Constraints
Examples
No public sample cases were explicitly marked for this problem in the original data.