Connection Status:
Competition Arena > MakingPotions

MakingPotions

SRM 433 · 2009-01-21 · by gojira_tc

SRM 433 · 2009-01-21 · by gojira_tc · Greedy, String Parsing
Class Name: MakingPotions
Return Type: int
Method Name: getCost
Arg Types: (vector<string>, vector<int>, vector<string>)
Problem Statement

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.

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.

Statement by TopCoder, Inc. — view the original on the archive.

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
78)
{"WATER"}
{1}
{"LOVE=1LOVE"}
Returns: -1

Some recipes can be useless.

Submissions are judged against all 116 archived test cases, of which 6 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class MakingPotions with a public method int getCost(vector<string> marketGoods, vector<int> cost, vector<string> recipes) · 116 test cases · 2 s / 256 MB per case

Submitting as anonymous