QuantumAlchemy
SRM 344 · 2007-03-28 · by Petr
Problem Statement
Consider 26 different substances, labeled 'A' through 'Z' (quotes for clarity only). Some of these substances can be created from the others by an alchemical reaction. Each alchemical reaction takes at least two different substances. Exactly 1 gram of each input substance is combined, causing an explosion. After the dust settles, we are left with just 1 gram of the resulting substance.
Alchemists don't like extra work, thus, for any given substance, there's at most one known reaction that results in that substance.
You are given a String initial describing the substances that you have initially. Each occurrence of a letter indicates 1 gram, so if a letter appears k times in initial, it means you have k grams of that substance. You are also given a String[] reactions describing all the possible alchemical reactions. Each element of reactions describes a single reaction and is formatted as "ingredients->result" (quotes for clarity only), where ingredients is the list of substances consumed and result is the substance produced. Return the minimal number of reactions required to obtain at least 1 gram of the substance 'X', or -1 if it is impossible.
Constraints
- initial will contain between 1 and 50 characters, inclusive.
- initial will contain only uppercase letters ('A'-'Z').
- reactions will contain between 1 and 26 elements, inclusive.
- Each element of reactions will contain between 5 and 28 characters, inclusive.
- Each element of reactions will be formatted as "ingredients->result" (quotes for clarity only).
- Each ingredients will be a string of distinct uppercase letters ('A'-'Z').
- Each result will be an uppercase letter ('A'-'Z').
- Each result will be distinct.
- Each ingredients will not contain the corresponding result.
"ABCDE"
{"ABC->F", "FE->X"}
Returns: 2
Some substances may be left unused.
"AABBB"
{"BZ->Y", "ZY->X", "AB->Z"}
Returns: 4
First, we make two grams of 'Z' by applying the last reaction twice. Second, we make 'Y' via the first reaction, and we still have 1 gram of 'Z' left, so that we can finally make 'X'.
"AAABB"
{"BZ->Y", "ZY->X", "AB->Z"}
Returns: -1
Not enough.
"AAXB"
{"BZ->Y", "ZY->X", "AB->Z"}
Returns: 0
No need to bother if we're already there.
"ABCDEFGHIJKLMNOPQRSTUVWYZABCDEFGHIJKLMNOPQRSTUVWYZ"
{"ABCE->Z", "RTYUIO->P", "QWER->T", "MN->B"}
Returns: -1
We have a lot of stuff and some reactions, but none of them results in 'X'.
Submissions are judged against all 173 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class QuantumAlchemy with a public method int minSteps(string initial, vector<string> reactions) · 173 test cases · 2 s / 256 MB per case