StampPads
SRM 158 · 2003-08-06 · by schveiguy
Problem Statement
Note to plugin users: there is an image in this problem statement. Please view the statement in the applet to see the image
There is a collection of multi-colored stamp pads at the local craft store. Each pad has 5 colors on it, arranged as pie wedges (see picture). The wedges can be switched out with other wedges, so you can create the ultimate blend of colors for your favorite stamp. You have a wish list of certain colors, but each pad set is expensive, so you want to minimize the cost. Given the colors of each pad and the colors you want, return the minimum number of pad sets that you must buy in order to get the right colors.
Here is an example of a stamp pad that you can buy:
You will be given a
"<color> <color> <color> <color> <color>"
Each <color> will be a
"yellow red purple blue cyan"
Each element of wishlist is a color that you wish to own. Your method should return the minimum number of pads you must buy to get all the colors in wishlist, or -1 if it is not possible to do.
Constraints
- pads will have between 1 and 20 elements, inclusive.
- Each element in pads will have between 9 and 50 characters, inclusive.
- Each element in pads will consist of exactly 5 color names separated by single spaces.
- Each color name in pads will have between 1 and 15 characters, inclusive, and will consist of only lowercase letters 'a'-'z', inclusive.
- There will be no repeated color names in a single element of pads
- wishlist will have between 1 and 25 elements, inclusive.
- Each element of wishlist will have between 1 and 15 characters, inclusive, and will consist of only lowercase letters 'a'-'z', inclusive.
- There will be no repeated elements in wishlist.
{"a b c d e", "b c d e f", "c d e f g", "d e f g h", "e f g h i", "f g h i j", "g h i j k", "h i j k l", "i j k l m", "j k l m n", "k l m n o", "l m n o p", "m n o p q", "n o p q r", "o p q r s", "p q r s t", "q r s t a", "r s t a b", "s t a b c", "t a b c d"}
{"a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s", "t"}
Returns: 4
{"yellow red purple blue cyan",
"red green orange magenta yellow",
"brown black orange yellow tan"}
{"orange", "yellow", "red", "blue", "magenta", "tan"}
Returns: 3
We can only get blue from the first pad, magenta from the second pad, and tan from the last. Therefore, all three must be purchased.
{"yellow red purple blue cyan",
"red green orange magenta yellow",
"brown black orange yellow tan"}
{"orange", "yellow", "red", "blue", "tan"}
Returns: 2
Although we can get orange and yellow from the second pad, we can get orange, yellow, and tan from the last, so the second is unnecessary.
{"yellow black blue green red",
"yellow brown cyan magenta tan",
"black grey fire maroon silver",
"blue white neon tangerine rust",
"green orange soot turquoise mint",
"red cream opal chrome sky"}
{"yellow", "black", "blue", "green", "red",
"brown", "grey", "white", "orange", "cream"}
Returns: 5
Although you can buy the first pad and get 5 colors on the wishlist, you still must buy the other 5 to get the rest of the colors. However, if you just buy the last 5 pads, you get all the colors.
{"red green orange magenta yellow"}
{"silver"}
Returns: -1
The single stamp pad available does not have silver, so the wishlist is impossible to fulfill.
Submissions are judged against all 66 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class StampPads with a public method int bestCombo(vector<string> pads, vector<string> wishlist) · 66 test cases · 2 s / 256 MB per case