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