TopCoder problem "SausagesProductionScheduler" used in TCCC07 Round 4 (Division I Level Two)



Problem Statement

    

You have several recipes for sausages, each of which use the same two ingredients, but possibly in different ratios. Each recipe contains a lower and upper bound for the percentage of each ingredient. This means you can use any percentages for the two ingredients as long as they add up to 100% and fall within the specified inclusive bounds.

The recipes are given as two String[]s lowerPercentage and upperPercentage. Each element in lowerPercentage and upperPercentage contains exactly two integers separated by a single space. The j-th integer in the i-th element of lowerPercentage is the lower percentage bound of ingredient j in the i-th recipe. The j-th integer in the i-th element of upperPercentage is the upper percentage bound of ingredient j in the i-th recipe.

You are given a int[] limits, the i-th element of which is the number of grams you have of ingredient i. Your goal is to make as many sausages as possible. Each sausage must weigh exactly 100 grams, and you may use each recipe at most once. Return the maximum number of sausages you can make.

 

Definition

    
Class:SausagesProductionScheduler
Method:maxCount
Parameters:String[], String[], int[]
Returns:int
Method signature:int maxCount(String[] lowerPercentage, String[] upperPercentage, int[] limits)
(be sure your method is public)
    
 

Constraints

-lowerPercentage will contain between 1 and 50 elements, inclusive.
-upperPercentage will contain the same number of elements as lowerPercentage.
-Each element of lowerPercentage and upperPercentage will consist of exactly two integers separated by a single space.
-Each integer in lowerPercentage and upperPercentage will be between 1 and 100, inclusive.
-Each integer in lowerPercentage will be less than or equal to the corresponding integer in upperPercentage.
-Each integer in lowerPercentage and upperPercentage will contain no leading zeroes.
-limits will contain exactly two elements.
-Each element of limits will be between 0 and 5000, inclusive.
 

Examples

0)
    
{"50 50"}
{"50 50"}
{100, 100}
Returns: 1
Only one sausage per recipe.
1)
    
{"41 33"}
{"57 40"}
{100, 150}
Returns: 0
You can't make a sausage using this recipe.
2)
    
{"40 21", "6 10"}
{"89 71", "87 62"}
{54, 69}
Returns: 1
You can make one sausage using either recipe, but not both.
3)
    
{"66 11", "9 11", "13 4"}
{"85 70", "28 41", "29 88"}
{280, 190}
Returns: 2
4)
    
{"39 19", "6 68", "62 28"}
{"64 78", "41 86", "72 98"}
{230, 232}
Returns: 3

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10924&pm=8205

Writer:

Mike Mirzayanov

Testers:

PabloGilberto , radeye , Olexiy , ivan_metelsky

Problem categories:

Dynamic Programming, Search