cho.shLoad Testing (Large)
For each case with known good load L and known bad load P, compute the worst-case number of adaptive tests that pins capacity within factor C.
Medium7Binary searchMathNo attempts yetTime limit5sMemory limit512 MBProblem
You run the website for a programming contest. Next year's contest is expected to draw P participants, so the site has to serve that many people at once.
From last year's contest you know the site handles at least L people at the same time with no errors, and you also know it cannot handle P people.
You want to pin the real capacity down within a factor of C. That means finding an integer a such that you know the site supports a people and you know it does not support a * C people.
You can run load tests. One load test picks an integer X and tells you whether the site supports at least X people. You choose each test after seeing the results of the earlier ones. If you play optimally, how many load tests do you need in the worst case?
Input
The first line has the number of test cases, T. Each of the next T lines has three space separated integers L, P and C in that order.
Limits
- 1≤T≤1000
- 2≤C≤10
- 1≤L<P≤109
- L, P and C are integers
Output
For each test case, print one line of the form "Case #x: y", where x is the case number starting from 1 and y is the number of load tests needed in the worst case to pin the capacity down within a factor of C.
Hint
In the second case of the first example, the site is known to support 19 people and known not to support 57 people. Those two numbers are already a factor of 3 apart, so no test is needed.
In the fourth case, suppose you test 48. If the site supports 48 people you still need another test, because 48 * 2 < 97. Suppose instead you test 49 and the site does not support 49 people. You still need another test, because 24 * 2 < 49. Two tests are enough.