TopCoder problem "MakingPotions" used in SRM 433 (Division II Level Three)



Problem Statement

    An old witch is making a love potion. She has a lot of recipes and each of them has the following form:



	S=N1S1+?+NkSk


where N1, ?, Nk are single-digit integers between 1 and 9, inclusive, S1, ?, Sk are names of ingredients, k is an integer greater than or equal to 1, and S is name of the resulting potion (all names contain only uppercase letters). This means that if she mixes N1 units of S1, ..., Nk units of Sk all together, she will obtain 1 unit of S. There may be multiple recipes for the same potion. In that case, the potion can be obtained using any one of them. The ingredients are also potions, and some of them can be bought at the market.



You want to create 1 unit of the potion called LOVE. You are given String[] recipes, each element of which is a recipe formatted as described above. You are also given a String[] marketGoods and a int[] cost. Each element of marketGoods is the name of a potion you can purchase at the market. The i-th element of cost is the cost of 1 unit of the i-th potion in marketGoods. Return the cheapest cost of obtaining 1 unit of LOVE. If this cost is greater than 1,000,000,000, return 1,000,000,001 instead. If the potion cannot be obtained, return -1 instead.
 

Definition

    
Class:MakingPotions
Method:getCost
Parameters:String[], int[], String[]
Returns:int
Method signature:int getCost(String[] marketGoods, int[] cost, String[] recipes)
(be sure your method is public)
    
 

Constraints

-marketGoods will contain between 1 and 50 elements, inclusive.
-Each element of marketGoods will contain between 1 and 50 characters, inclusive.
-Each element of marketGoods will contain only uppercase letters ('A'-'Z').
-All elements of marketGoods will be distinct.
-cost will contain the same number of elements as marketGoods.
-Each element of cost will be between 1 and 100, inclusive.
-recipes will contain between 0 and 50 elements, inclusive.
-Each element of recipes will contain between 4 and 50 characters, inclusive.
-Each element of recipes will contain only uppercase letters ('A'-'Z'), non-zero digits ('1'-'9') and the characters '+' and '='.
-Each element of recipes will be formatted as described in the problem statement.
 

Examples

0)
    
{"LOVE", "WATER", "HONEY"}
{100, 1, 30}
{"LOVE=5WATER+3HONEY"}
Returns: 95
The LOVE potion is sold at the market, but the witch can make it for a lower cost.
1)
    
{"WATER", "HONEY", "HOP"}
{2, 6, 9}
{"LOVE=2WATER+4HONEY+2BEER", "BEER=1HOP+3WATER+1HOP"}
Returns: 76
To obtain LOVE, one must make two units of BEER at a cost of 24 each, and then mix 2 units of WATER, 4 units of HONEY and 2 units of BEER, which will cost a total of 76.
2)
    
{"ORANGEJUICE", "APPLEJUICE"}
{6, 4}
{"JUICEMIX=1ORANGEJUICE+1APPLEJUICE"}
Returns: -1
The witch doesn't have a LOVE recipe.
3)
    
{"WATER", "HONEY", "HOP"}
{1,22,17}
{"LOVE=7WATER+3HONEY", "LOVE=2HONEY+2HOP"}
Returns: 73
The witch has two LOVE recipes and prefers the first one.
4)
    
{"OIL", "WATER"}
{60, 70}
{"FIRSTPOTION=1OIL+1SECONDPOTION", "SECONDPOTION=4WATER+1FIRSTPOTION", "LOVE=1FIRSTPOTION+1SECONDPOTION"}
Returns: -1
5)
    
{"HONEYBIT"}
{100}
{"LOVE=6HONEYMEGABYTE","HONEYMEGABYTE=2HONEYFIFTYTWELVEKBYTES",
"HONEYFIFTYTWELVEKBYTES=8HONEYSIXTYFOURKBYTES","HONEYSIXTYFOURKBYTES=8HONEYEIGHTKBYTES",
"HONEYEIGHTKBYTES=8HONEYKBYTE","HONEYKBYTE=2EIGHTBYEIGHTWORDS","EIGHTBYEIGHTWORDS=8EIGHTWORDS",
"EIGHTWORDS=8HONEYWORD","HONEYWORD=8HONEYBYTE","HONEYBYTE=8HONEYBIT"}
Returns: 1000000001
6)
    
{"WATER"}
{1}
{"LOVE=1LOVE"}
Returns: -1
Some recipes can be useless.
7)
    
{"MILK","WATER","HOP"}
{6,1,14}
{"NECTAR=4HOP+2MILK","LOVE=5MILK+3BEER","LOVE=2WATER+1LOVE","LOVE=2MIX+1NECTAR",
"MIX=1MILK+1WATER+1HOP","BEER=5WATER+2HOP","LOVE=1NECTAR+3WATER+3HOP","NECTAR=3BEER+1MILK+2MILK"}
Returns: 110

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=10009

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=13695&pm=10009

Writer:

gojira_tc

Testers:

PabloGilberto , Olexiy , ivan_metelsky

Problem categories:

Greedy, String Parsing