Destruction
TCO07 Round 1A · 2007-03-07 · by dgoodman
Problem Statement
We can run multiple tests. Each test can test only a single pressure on a single container, and the result of a test is either that the container survived or was destroyed. If it survived it can be used in successive tests.
We must develop a testing protocol that uses no more than numTests tests and destroys no more than numDestroyed containers. The testing must determine whether or not the container can withstand 100.0, and if it cannot it must also estimate the critical pressure as accurately as possible. Given numTests and numDestroyed return the minimum absolute error we can guarantee in our estimate of critical pressure.
Notes
- A return value with either an absolute or relative error of less than 1.0E-9 is considered correct.
Constraints
- numTests will be between 1 and 50, inclusive.
- numDestroyed will be between 1 and numTests, inclusive.
1 1 Returns: 50.0
If the one test is at a pressure lower than 100.0 and the container survives, we won't know whether or not the container can survive pressures greater than 100. So the one test must be at a pressure of 100.0. If the container does not survive the test, then we can estimate the critical pressure at 50.0, with a possible error of +- 50.0.
3 1 Returns: 16.666666666666664
First test pressure = 33.3333333. If the test container is destroyed, the estimate is 16.66666667 with an error of +-16.6666667. If the container survives the first test, we can run a second test at 66.666667. If the container is destroyed, our estimate is 50.0. Otherwise we run our last test at 100.0 to determine whether to estimate 83.33333 or to report that these containers can survive more than 100.0.
20 3 Returns: 0.03703703703704745
50 50 Returns: 4.440892098505072E-14
50 2 Returns: 0.039215686274512815
Submissions are judged against all 46 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class Destruction with a public method double minError(int numTests, int numDestroyed) · 46 test cases · 2 s / 256 MB per case