Connection Status:
Competition Arena > SausagesProductionScheduler

SausagesProductionScheduler

TCCC07 Sponsor 4 · 2007-07-30 · by Mike Mirzayanov

TCCC07 Sponsor 4 · 2007-07-30 · by Mike Mirzayanov · Dynamic Programming, Search
Class Name: SausagesProductionScheduler
Return Type: int
Method Name: maxCount
Arg Types: (vector<string>, vector<string>, vector<int>)
Problem Statement

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.

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

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

Coding Area

Language: C++17 · define a public class SausagesProductionScheduler with a public method int maxCount(vector<string> lowerPercentage, vector<string> upperPercentage, vector<int> limits) · 130 test cases · 2 s / 256 MB per case

Submitting as anonymous