TopCoder problem "ForceTest" used in SRM 276 (Division I Level Three)



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.

 

Definition

    
Class:ForceTest
Method:fewestTests
Parameters:int, int
Returns:int
Method signature:int fewestTests(int maxForce, int testUnits)
(be sure your method is public)
    
 

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)
    
100
2
Returns: 101

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=5934

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=8073&pm=5934

Writer:

timmac

Testers:

PabloGilberto , brett1479 , Olexiy

Problem categories:

Dynamic Programming, Math, Search, Simulation