Problem G
Stoichiometry
You have landed a lucrative contract with Amalgamated Chemical Manufacturing (ACM), to help their chemists with stoichiometry. Stoichiometry is the calculation of reactants and products in chemical reactions, based on the law of conservation of mass, which states that the total mass of the reactants equals the total mass of the products. The relations among quantities of reactants and products typically form a ratio of positive integers. If the amounts of the separate reactants are known, then the amount of the product can be calculated, and vice-versa. The relationship of reactants to products can be described using a soichiometric equation such as:
\begin{equation} \rm {C H_4 + 2 O_2 \rightarrow C O_2 + 2 H_2 O}, \end{equation}which can be read as: “One molecule of $\rm C H_4$ and two molecules of $\rm O_2$ yield one molecule of $\rm C O_2$ and two molecules of $\rm H_2 O$.” The total number of atoms of each element on the left hand side of the stoichiometric equation must match the number of atoms of that element on right hand side. Your task is to write a program that, given an equation of the form:
\begin{equation} \rm {\_ H_2 O + \_ C O_2 \rightarrow \_ O_2 + \_ C_6 H_{12} O_6}, \label{exampleeq} \end{equation}will fill in the blanks to produce a balanced equation. For example, the above equation could be balanced as follows:
\begin{equation} \rm {6H_2O + 6CO_2 \rightarrow 6O_2 + 1C_6H_{12}O_6}. \end{equation}Input
An equation is input in the form of a sequence of $M$ $(1 < M \le 20)$ lines, one for each molecule in the formula (e.g., $\rm {H_2 O}$ or $\rm {CO_2}$). Each line $m$ ($1\le m \le M$) has the following fields:
\begin{equation*} sign_ m\; \; N_ m\; \; element_{m,1}\; \; count_{m,1}\; \; \ldots \; \; element_{m,{N_ m}}\; \; count_{m,{N_ m}} \end{equation*}where $sign_ m$ is either +1 or -1, with a sign of +1 indicating that this molecule appears on the left of the equation, and -1 indicating that it appears on the right. $N_ m$, where $0 < N_ m < 20$, is the number of $element$/$count$ pairs following on the line. Each $element_{m,n}$, where $1 \le n \le N_ m$, is an element name consisting of one or two upper or lowercase letters, and each $count_{m,n}$ is a positive integer, $1 \leq count_{m,n} \leq 12$. For example, the element/count pair “Fe 2” indicates that the molecule contains two atoms of the element Fe (iron). There will be no more than 10 unique elements in a single equation.
Note that an element may be repeated in a given line of
input, as in
+1 6 C 1 H 5 C 1 O 1 O 1 H 1
which specifies that at least one molecule of $\rm CH_5COOH$ appears on the left
side of the equation. Note that $\rm CH_5COOH$ can be written as
$\rm C_2H_6O_2$.
Input ends with a line of the form
0 0
Output
The program must output the numbers $C_1,\ldots ,C_ M$ $(0<C_ i\le 1\, 000)$, in order, to fill in the blanks in the equation. Each number, $C_ m\mid 1\le m \le M$, must be the minimum number for which the equation is balanced (i.e. there is no common factor that could reduce all of the $C_ m$ coefficients). You may assume that every input test case has exactly one valid solution meeting these criteria.
| Sample Input 1 | Sample Output 1 |
|---|---|
+1 2 H 2 O 1 +1 2 C 1 O 2 -1 1 O 2 -1 3 C 6 H 12 O 6 0 0 |
6 6 6 1 |
| Sample Input 2 | Sample Output 2 |
|---|---|
+1 5 Be 2 C 1 O 3 O 2 H 2 +1 3 Ac 1 O 1 H 1 -1 4 Be 4 O 1 Ac 6 O 6 -1 2 H 2 O 1 -1 2 C 1 O 2 0 0 |
2 6 1 5 2 |
