Here I have a problem in understanding the optimal testing strategy.

In a scenario, You have been given two laptop batteries and a testing device. The testing device will make the battery connected to it (one battery can be connected at a time) deliver x mA, where x is an integer. The testing device is constructed in such a way that the battery will always explode if there’s any risk of explosion at that current.

Now we want a program that receives inputs. Input consists of multiple lines, one line per case (at most 200 test cases). Each line contains a single positive integer n between 1 and 4711 inclusive, giving the current at which the battery is known to explode. Input is terminated by a line containing 0, which should not produce any output.

And produce Output, where for each case, print one line containing the worst-case number of tests to perform when using an optimal testing strategy.

|  Sample Input   |  Sample Output   |
|--------- -------|------------------|
    1                0
    2                1
    10               4
    23               7

This was a programming contest question marked as an easy question. but I do not get the definition of the optimal testing strategy. What can be the boundaries? Generally what this question means?

  • 2
    $\begingroup$ I have a feeling that you haven't described the complete problem. As stated, it is not clear what is a testing strategy, so the question is unanswerable. $\endgroup$ – Yuval Filmus Jan 30 '19 at 5:12
  • 2
    $\begingroup$ Please add a reference to the original source in the question. $\endgroup$ – John L. Jan 30 '19 at 5:56

in my opinion, The designer of this question just wanted to make a famous algorithm problem a bit complicated but made it totally nonsense.

This is the famous two egg problem where

You are given two eggs and access to a 100-story building. Both eggs are identical. The aim is to find out the highest floor from which an egg will not break when dropped out of a window from that floor. If an egg is dropped and does not break, it is undamaged and can be dropped again. However, once an egg is broken, that’s it for that egg.

| cite | improve this answer | |
  • $\begingroup$ Not sure how you'd get to the answers above using the the equation from "The two egg problem"? Square root in this case should be 96.568, so for example not sure how that would allow you figure out that 9 is the optimal current for input 10 by performing only 4 checks? $\endgroup$ – Todor Kolev May 18 at 13:06
  • $\begingroup$ @TodorKolev you start at 4, (4+ 3), (4 +3 +2), (4 +3 + 2+ 1) currents ? that is, 4, 7, 9, 10 in the worst case ? So the answer is 4 ? $\endgroup$ – tonythomas01 May 31 at 8:40
  • $\begingroup$ Also, how do you select the right root to chose to as the starting floor ? I see that the link you have pointed to just uses the positive roots. However, when you have say 17, you have roots as 5.352349955359813, and -6.352349955359813. How do we deal with this ? The answer seems to be 6 in this case. $\endgroup$ – tonythomas01 May 31 at 19:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.