PROBLEM STATEMENT
You have just begun working as a grocery bagger at the local TopGrocer food store. Your job is to
place all of a customer's items into bags, so they can be carried from the store. Your manager
has instructed you to use as few bags as possible, to minimize the store's overall cost. However,
for the customer's convenience, you are instructed that only items of the same type can be placed
in the same bag. For instance, a produce item can be bagged with any other produce items, but not
with dairy items.
You are given a vector itemType indicating the type of each item that needs to be bagged.
You are also given an int strength indicating the maximum number of items that can be placed in
each bag. You are to return an int indicating the minimum number of bags required to package the
customer's items.
DEFINITION
Class:GroceryBagger
Method:minimumBags
Parameters:int, vector
Returns:int
Method signature:int minimumBags(int strength, vector itemType)
CONSTRAINTS
-strength will be between 1 and 50, inclusive.
-itemType will contain between 0 and 50 elements, inclusive.
-Each element of itemType will contain between 1 and 50 characters, inclusive.
-Each element of itemType will contain only the characters 'A'-'Z'.
EXAMPLES
0)
2
{"DAIRY",
"DAIRY",
"PRODUCE",
"PRODUCE",
"PRODUCE",
"MEAT"}
Returns: 4
Here, you have six items. You could put two items in each bag, but you would have to mix item
types. The single meat item must get its own bag. The two dairy items fit in one bag. The three
produce items will require two bags.
1)
3
{"DAIRY",
"DAIRY",
"PRODUCE",
"PRODUCE",
"PRODUCE",
"MEAT"}
Returns: 3
Similar to above, but now we have stronger bags. Note again, though, that if we were allowed to
mix item types, we could get away with only 2 bags. But since item types cannot be mixed, we need
3 bags.
2)
10
{}
Returns: 0
The bags are really strong, but we didn't buy anything.
3)
5
{"CANNED", "CANNED", "PRODUCE",
"DAIRY", "MEAT", "BREAD",
"HOUSEHOLD","PRODUCE", "FROZEN",
"PRODUCE", "DAIRY"}
Returns: 7
Notice that a customer doesn't necessarily pay for the items in any particular order, but the
bagger still has to be responsible for sorting them out. In this case, though, one bag for each
item type suffices.
4)
2
{"CANNED", "CANNED", "PRODUCE",
"DAIRY", "MEAT", "BREAD",
"HOUSEHOLD","PRODUCE", "FROZEN",
"PRODUCE", "DAIRY"}
Returns: 8
As above, but our produce requires two bags now.
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.