BirthdayCake
SRM 422 · 2008-10-18 · by mateuszek
SRM 422 · 2008-10-18 · by mateuszek · Brute Force, String Manipulation, String Parsing
Problem Statement
Problem Statement
You are going to make a fruit birthday cake for a party. There are several kinds of fruit you can choose from, and you must choose at least K different kinds to put on the cake. However, some of your friends don't like certain kinds of fruits, and they will refuse to eat a cake containing any of those fruits. You want as many of your friends as possible to eat the cake.
You are given aString[] availableFruits, where each element is a kind of fruit that you can put on the cake. You are also given a String[] friendsDislikings, where each element is a space-separated list of the kinds of fruits that one of your friends doesn't like. Return the largest number of friends that can eat the cake, assuming that you must use at least K different kinds of fruits.
You are given a
Constraints
- availableFruits will contain between 1 and 50 elements, inclusive.
- Each element of availableFruits will contain between 1 and 50 characters, inclusive.
- Each element of availableFruits will contain only lowercase letters ('a' - 'z').
- All elements of availableFruits will be distinct.
- friendsDislikings will contain between 1 and 20 elements, inclusive.
- Each element of friendsDislikings will contain between 1 and 50 characters, inclusive.
- Each element of friendsDislikings will be a space-separated list of fruit names without any leading or trailing spaces.
- Each fruit name in each element of friendsDislikings will consist of lowercase letters ('a' - 'z') only.
- Fruit names in each element of friendsDislikings will all be distinct.
- K will be between 1 and the number of elements in availableFruits, inclusive.
Examples
0)
{ "apple", "orange", "strawberry", "cherry" }
{ "apple orange", "apple cherry", "strawberry orange", "cherry", "apple" }
2
Returns: 3
You can make your cake using strawberries and oranges and friends 1, 3 and 4 (0-based) will eat it.
1)
{ "strawberry", "orange", "apple", "lemon", "watermelon" }
{ "orange", "apple", "lemon", "watermelon" }
1
Returns: 4
A strawberry cake is a perfect match here.
2)
{ "apple", "orange" }
{ "strawberry" }
2
Returns: 1
Note that friends may dislike a fruit you don't even have.
3)
{"melon","watermelon"}
{"watermelon"}
1
Returns: 1
4)
{"a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y",
"aa","bb","cc","dd","ee","ff","gg","hh","ii","jj","kk","ll","mm","nn","oo","pp","qq","rr","ss","tt","uu","vv","ww","xx","yy"}
{"a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t"}
1
Returns: 20
Submissions are judged against all 81 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class BirthdayCake with a public method int howManyFriends(vector<string> availableFruits, vector<string> friendsDislikings, int K) · 81 test cases · 2 s / 256 MB per case