Connection Status:
Competition Arena > ForceTest

ForceTest

SRM 276 · 2005-12-08 · by erinn

SRM 276 · 2005-12-08 · by erinn · Dynamic Programming, Math, Search, Simulation
Class Name: ForceTest
Return Type: int
Method Name: fewestTests
Arg Types: (int, int)
Problem Statement

Problem Statement

Your company produces components used in construction. From time to time, it is necessary to run a series of tests on several of the components, to determine their breaking force. The goal of the testing is to determine the point at which the unit breaks, up to a given threshold. (Only integer forces are applied.)

You have a set of components to be used for testing. You are to find an optimal testing plan, minimizing the number of tests that will have to be performed (in the worst case). In the process of testing, you may destroy some or all of the test components, provided that in the end, the breaking force is known.

Unfortunately, no manufacturing process is perfect, so it is possible that one of your test components is defective. A defective component is defined as one that breaks under a lesser force than a typically produced component.

You are given int maxForce, the highest force at which you need to test the components. (They may have a higher breaking force than this, but you are not concerned with testing any higher force.) You are also given int testUnits, the number of units that are available for testing. You are to return the fewest number of tests necessary to conclusively determine the breaking force of a non-defective component.

Notes

  • Assume that the (non-defective) component has a fixed breaking point. That is, if it breaks when tested at a given force, it will break whenever tested with a greater force. Likewise, if it passes testing for a given force, it will pass for any lower force.
  • The testing strategy may destroy all of the components that were made available for testing, as long as it finds the exact breaking force of the non-defective component.
  • All of the test components, except for possibly a single defective one, are identical, and will break under the same force.
  • It is not necessarily the case that one of the test components is defective, however, there will never be more than one defective component.
  • A defective component will always break under a lower force than a normal component.

Constraints

  • maxForce will be between 1 and 100, inclusive.
  • testUnits will be between 2 and 20, inclusive.
Examples
0)
1
2
Returns: 2

We have to do a maximum of two tests. If the first test should fail, we need to test the second unit to determine if the first was defective.

1)
2
2
Returns: 3

Here, we have to start by testing a force of 1. If the unit breaks, we have to retest with a force of 1 to determine if the first was a defect. Then, if the second test passes, we need a third test to determine if the good unit can withstand a force of 2. Notice that if we had tested the first component with a force of 2, and it had failed, we would have only had a single unit left, and would not have been able to determine if a defective unit was present.

2)
10
4
Returns: 6
3)
30
4
Returns: 8
4)
100
2
Returns: 101

Submissions are judged against all 103 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class ForceTest with a public method int fewestTests(int maxForce, int testUnits) · 103 test cases · 2 s / 256 MB per case

Submitting as anonymous