Balls#2442
The classic Two Glass Balls brain-teaser is often posed as:
Given two identical glass spheres, you would like to determine the lowest floor in a -story building from which they will break when dropped. Assume the spheres are undamaged when dropped below this point. What is the strategy that will minimize the worst-case scenario for number of drops?
Suppose that we had only one ball. We'd have to drop from each floor from to in sequence, requiring drops in the worst case.
Now consider the case where we have two balls. Suppose we drop the first ball from floor . If it breaks, we're in the case where we have one ball remaining and need to drop from floors to n-1 in sequence, yielding drops in the worst case (the first ball is dropped once, the second at most n-1 times). However, if it does not break when dropped from floor , the problem is reduced to dropping from floors n+1 to . In either case, we must keep in mind that we've already used one drop. So the minimum number of drops, in the worst case, is the minimum over all .
You will write a program to determine the minimum number of drops required, in the worst case, given balls and an -story building.
The first line of input contains a single integer (1 \leq P \leq 1000), which is the number of data sets that follow. Each data set consists of a single line containing three () decimal integer values: the problem number, followed by a space, followed by the number of balls (1 \leq B \leq 50), followed by a space, and the number of floors in the building (1 \leq M \leq 1000).
For each data set, generate one line of output with the following values: the data set number as a decimal integer, a space, and the minimum number of drops needed for the corresponding values of and .
Example 1