PROBLEM STATEMENT
It's Monday afternoon at Happy Burger, the happiest fast food restaurant in
town. You and your buddies decide to ditch work and fill up on some good
greasy food. After everybody decides what they want from the menu, you wonder
if it would be cheaper to pool all your orders together and take advantage of
Happy Burger's specially priced value combos. For example, consider the
following scenario:
Clint wants a TripleDeluxeBurger. Martina wants the SuperSpicyCurlyFries.
Wayne wants a StrawberrySundae. Garth isn't hungry, and he just wants a
DietSoda. The menu shows the following items:
TripleDeluxeBurger $1.50
SuperSpicyCurlyFries $1.00
StrawberrySundae $1.00
DietSoda $1.50
Combo #1 (TripleDeluxeBurger, SuperSpicyCurlyFries, StrawberrySundae, DietSoda)
$4.00
You notice that the Combo #1 would satisfy everybody's order, and the total
price would be $1.00 cheaper than buying each item separately. With this
knowledge, you take everybody's money, offer to order for them while they find
seats, and then pocket the money you save.
Implement a class FastFood, which contains a method cheapest. This method will
return the cheapest total cost (in cents) required to buy all the items
desired. You are given two inputs: a String[] representing the items desired
by your friends, and a String[] representing the prices for all the items and
combos on the menu.
The items desired by your friends will be formatted as follows: Each element of
the String[] will represent a single desired item. Each item is a single word
that contains only letters - no leading/trailing spaces are allowed. Items are
case-sensitive - "Burger" refers to a different item than "burger". Example:
Angus wants a "Burger" and a "Shake". Malcolm wants a "Cheeseburger". The
String[] looks like {"Burger", "Shake", "Cheeseburger"}. There can be no blank
items in the String[].
The menu entries will be formatted as follows: Each element of the String[]
will represent a single menu entry. Each entry will be represented as a String
containing one or more items, followed by a price (in cents) representing the
cost of all those items combined. Each item in the entry will be separated by
a single space, and the last item and the price will be separated by a single
space (again, there are no leading/trailing spaces in the String). Each price
will be an int and can contain leading zeros. Example: A "Burger" costs $0.50.
A "Shake" costs $1.00. A "Burger" and a "Shake" together costs $1.25. The
menu might look like {"Burger 50", "Shake 0100", "Burger Shake 125"}.
All the items desired by your friends will exist on the menu. You must buy all
the items desired. By buying combos to get a cheaper price, you may end up
with items that nobody wanted - that's okay.
DEFINITION
Class: FastFood
Parameters: String[], String[]
Returns: int
Method signature (be sure your method is public): int cheapest(String[] items,
String[] menu);
INPUT CONSTRAINTS
TopCoder will verify that all input constraints are met.
- all menu entries will cost between 0 and 1000 cents inclusive.
- menu will contain between 0 and 50 elements inclusive.
- each element of menu will contain between 0 and 50 characters inclusive.
- items will contain between 0 and 12 elements inclusive.
- each element of items will contain between 1 and 50 characters inclusive.
- all food items referenced in items will exist in menu.
- each food item will appear in no more than 4 menu entries (but within each of
those entries, it can appear multiple times).
- no two menu elements will contain the same exact food items (for example, the
following will not occur: {"burger fries 200", "fries burger 199"}
- each food item will only contain letters (a-z,A-Z).
NOTES
- each food item will not necessarily appear as an individual menu entry by
itself (not in a combo)
- combo meals will not necessarily cost less than the sum of its individual items
EXAMPLES:
items: {}
menu: {"Burger 100"}
return value: 0
---------------------
items: {"Burger", "Fries", "ChickenSandwich", "Fries", "Drink", "Drink"}
menu: {"Burger 50", "Fries 50", "ChickenSandwich 100", "Drink 75", "Burger
Fries 75", "Burger Fries Drink 145", "ChickenSandwich Fries Drink 200"}
The cheapest way to satisfy this order is to buy the last two things on the
menu for a total of $3.45.
return value: 345
---------------------
items: {"HamSandwich", "Drink"}
menu: {"HamSandwich Salad 175", "HamSandwich HamSandwich Drink 275", "Drink 75"}
Best thing to do here is to buy the HamSandwich and Salad combo along with a
Drink for $2.50. You'll be stuck with an unwanted Salad, but that's okay.
return value: 250