SandwichBar
SRM 277 · 2005-12-17 · by lovro
SRM 277 · 2005-12-17 · by lovro · Simple Search, Iteration, String Parsing
Problem Statement
Problem Statement
It's time to get something to eat and I've come across a sandwich bar. Like most people, I prefer certain types of sandwiches. In fact, I keep a list of the types of sandwiches I like.
The sandwich bar has certain ingredients available. I will list the types of sandwiches I like in order of preference and buy the first sandwich the bar can make for me. In order for the bar to make a sandwich for me, it must include all of the ingredients I desire.
Given a
Constraints
- available will contain between 1 and 50 elements, inclusive.
- Each element of available will contain between 1 and 50 lowercase letters ('a' - 'z'), inclusive.
- orders will contain between 1 and 50 elements, inclusive.
- Each element of orders will contain between 1 and 50 lowercase letters ('a' - 'z') and spaces, inclusive.
- Each element of orders will represent a list of desired ingredients separated by single spaces, with no leading or trailing spaces.
Examples
0)
{ "ham", "cheese", "mustard" }
{ "ham cheese" }
Returns: 0
I only like plain ham and cheese sandwiches, and since both ham and cheese are available, I'll take that.
1)
{ "cheese", "mustard", "lettuce" }
{ "cheese ham", "cheese mustard lettuce", "ketchup", "beer" }
Returns: 1
They've run out of ham, but I'll consider other options now.
2)
{ "cheese", "cheese", "cheese", "tomato" }
{ "ham ham ham", "water", "pork", "bread", "cheese tomato cheese", "beef" }
Returns: 4
Ignore any duplicate elements in the lists.
3)
{ "foo", "bar", "baz", "gazonk", "quux", "bat", "xyzzy",
"shme", "hukarz", "grault", "waldo", "bleh" }
{ "kalatehas", "spam eggs", "needle haystack", "bleh blarg", "plugh",
"the best sandwich in the universe" }
Returns: -1
4)
{ "a", "a", "c", "b", "a", "b", "b" }
{ "a b c d", "d c b a", "c b a", "a a a a b b b b b b b b b b", "a a b b c", "a b c" }
Returns: 2
6)
{ "ingredientwithalongnamepossiblynotverytastyoratall", "ingredientnolongerthanthepreviousbutmuchtastierrrr", "ingredientnolongerthanthepreviousbutmuchtastierrra", "ingredientnolongerthanthepreviousbutmuchtastierrrb", "ingredientnolongerthanthepreviousbutmuchtastierrrc", "ingredientnolongerthanthepreviousbutmuchtastierrrd", "ingredientnolongerthanthepreviousbutmuchtastierrre", "ingredientnolongerthanthepreviousbutmuchtastierrrf", "ingredientnolongerthanthepreviousbutmuchtastierrrg", "ingredientnolongerthanthepreviousbutmuchtastierrrh", "ingredientnolongerthanthepreviousbutmuchtastierrri", "ingredientnolongerthanthepreviousbutmuchtastierrrj", "ingredientnolongerthanthepreviousbutmuchtastierrrk", "ingredientnolongerthanthepreviousbutmuchtastierrrl", "ingredientnolongerthanthepreviousbutmuchtastierrrm", "ingredientnolongerthanthepreviousbutmuchtastierrrn", "ingredientnolongerthanthepreviousbutmuchtastierrro", "ingredientnolongerthanthepreviousbutmuchtastierrrp", "ingredientnolongerthanthepreviousbutmuchtastierrrq", "ingredientnolongerthanthepreviousbutmuchtastieoops", "ingredientnolongerthanthepreviousbutmuchtastierrrs", "ingredientnolongerthanthepreviousbutmuchtastierrrt", "ingredientnolongerthanthepreviousbutmuchtastierrru", "ingredientnolongerthanthepreviousbutmuchtastierrrv", "ingredientnolongerthanthepreviousbutmuchtastierrrw", "ingredientnolongerthanthepreviousbutmuchtastierrrx", "ingredientnolongerthanthepreviousbutmuchtastierrry", "ingredientnolongerthanthepreviousbutmuchtastierrrz", "ingredientnolongerthanthepreviousbutmuchtastierrta", "ingredientnolongerthanthepreviousbutmuchtastierrtb", "ingredientnolongerthanthepreviousbutmuchtastierrtc", "ingredientnolongerthanthepreviousbutmuchtastierrtd", "ingredientnolongerthanthepreviousbutmuchtastierrte", "ingredientnolongerthanthepreviousbutmuchtastierrtf", "ingredientnolongerthanthepreviousbutmuchtastierrtg", "ingredientnolongerthanthepreviousbutmuchtastierrth", "ingredientnolongerthanthepreviousbutmuchtastierrti", "ingredientnolongerthanthepreviousbutmuchtastierrtj", "ingredientnolongerthanthepreviousbutmuchtastierrtk", "ingredientnolongerthanthepreviousbutmuchtastierrtl", "ingredientnolongerthanthepreviousbutmuchtastierrtm", "ingredientnolongerthanthepreviousbutmuchtastierrtn", "ingredientnolongerthanthepreviousbutmuchtastierrto", "ingredientnolongerthanthepreviousbutmuchtastierrtp", "ingredientnolongerthanthepreviousbutmuchtastierrtr", "ingredientnolongerthanthepreviousbutmuchtastierrts", "ingredientnolongerthanthepreviousbutmuchtastierrtu", "ingredientnolongerthanthepreviousbutmuchtastierrtw", "ingredientnolongerthanthepreviousbutmuchtastierrtx", "ingredientnolongerthanthepreviousbutmuchtastierrty" }
{ "a b c d e f g h i j k l m n o p q r s t u v w x yz", "i know the alphabet", "ingredientnolongerthanthepreviousbutmuchtastierrxx", "a b c d e f g h i j k l m n o p q r s t u v w x yz", "i know the alphabet", "ingredientnolongerthanthepreviousbutmuchtastierftf", "out of bounds out of bounds out of bounds out of", "abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwx", "abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwx", "abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwx", "abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwx", "abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwx", "abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwx", "abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwx", "abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwx", "abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwx", "abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwx", "abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwx", "abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwx", "abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwx", "abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwx", "abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwx", "abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwx", "abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwx", "abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwx", "abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwx", "abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwx", "abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwx", "abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwx", "abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwx", "abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwx", "abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwx", "abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwx", "abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwx", "abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwx", "abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwx", "abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwx", "abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwx", "abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwx", "abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwx", "abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwx", "abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwx", "a b c d e f g h i j k l m n o p q r s t u v w x yz", "a b c d e f g h i j k l m n o p q r s t u v w x yz", "a b c d e f g h i j k l m n o p q r s t u v w x yz", "a b c d e f g h i j k l m n o p q r s t u v w x yz", "a b c d e f g h i j k l m n o p q r s t u v w x yz", "a b c d e f g h i j k l m n o p q r s t u v w x yz", "yay for domino day", "ingredientnolongerthanthepreviousbutmuchtastierrtf" }
Returns: 49
large input
Submissions are judged against all 30 archived test cases, of which 6 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class SandwichBar with a public method int whichOrder(vector<string> available, vector<string> orders) · 30 test cases · 2 s / 256 MB per case