Safety in Alchemy
InterviewTime limit1sMemory limit128 MB
Given reaction heats between pairs of chemicals and limited amounts of each chemical, find the maximum total heat that can be produced.
- Level
Medium7 of 10
- Topics
- Graph, Dynamic programming, Brute force, Greedy
- Solved
- No attempts yet
Problem
Frederico de Vinci (one of Leonardo's less talented cousins) is a budding alchemist who spends his days mixing all sorts of chemicals, hoping to stumble upon the formula that turns lead into gold. Beside his worktable he keeps a cheap ceramic jar into which he tosses the useless and rather noxious results of his failed experiments.
The heat given off by the chemicals reacting in that jar has already caused a few accidents, cracking and even shattering his disposal jars.
Frederico has compiled a table of the temperature changes produced by various pairs of chemicals he has previously dropped into his disposal jars. (He believes that simultaneous interactions of three or more chemicals are insignificant.) For each pair, the table gives the temperature rise, in whole degrees, produced when 1 gram of the first chemical reacts with 1 gram of the second. Each such reaction consumes 1 gram of each chemical, and any given gram of a chemical can take part in at most one reaction.
Given this table and the list of chemicals (with quantities) that Frederico plans to drop into the jar, compute the maximum total temperature rise the contents may produce.
Input
The input consists of one or more problem sets. The last problem set is followed by a line containing only the word ENDOFINPUT.
Each problem set begins with a list of up to 64 chemical pairs and the heat they produce. Each line has the form
chemical1 chemical2 heat
where chemical1 and chemical2 are chemical names, each an alphabetic string of 1 to 20 characters, and heat is an integer from 0 to 100 giving the number of degrees the jar's temperature rises when 1 gram of chemical1 reacts with 1 gram of chemical2. The order of the two names on a line does not matter, and no pair of chemicals appears more than once. This list is terminated by a line containing 0 0 0.
Next comes a list of up to 12 chemicals that Frederico plans to place in the jar. Each line has the form
chemical amount
where chemical is a chemical name (again an alphabetic string of 1 to 20 characters) and amount is an integer from 0 to 1000 giving the quantity in grams. No chemical appears more than once in this list. This list is terminated by a line containing 0 0.
Output
For each problem set, print a single line of the form
The temperature in the jar will change by at most M degrees.
where M is the maximum total temperature rise, an integer.