prithivMLmods/Coder-Stat

1 2<H1><font color="#000">Problem F:</font> Chemist's Math</H1>3 4<p>5You have probably learnt chemical equations (chemical reaction formulae) in your high-school6days. The following are some well-known equations.7</p>8 9<pre><font face="Times New Roman">10                                         2H<sub>2</sub> + O<sub>2</sub> &rarr; 2H<sub>2</sub>O                                              (1)11                                         C<sub>a</sub>(OH)<sub>2</sub> + CO<sub>2</sub> &rarr; C<sub>a</sub>CO<sub>3</sub> + H<sub>2</sub>O                      (2)12                                         N<sub>2</sub> + 3H<sub>2</sub> &rarr; 2NH<sub>3</sub>                                              (3)13</font>14</pre>15 16<p>17While Equations (1)–(3) all have balanced left-hand sides and right-hand sides, the following18ones do not.19</p>20<pre>21<font face="Times New Roman">22                                         Al + O<sub>2</sub> &rarr; Al<sub>2</sub>O<sub>3</sub>    (<i>wrong</i>)                                (4)23                                         C<sub>3</sub>H<sub>8</sub> + O<sub>2</sub> &rarr; CO<sub>2</sub> + H<sub>2</sub>O (<i>wrong</i>)                     (5)24</font>25</pre>26 27<p>28 29The equations must follow <i>the law of conservation of mass</i>; the quantity of each chemical element30(such as H, O, Ca, Al) should not change with chemical reactions. So we should "adjust" the31numbers of molecules on the left-hand side and right-hand side:32</p>33 34<pre>35<font face="Times New Roman">36                                        4Al + 3O<sub>2</sub> &rarr; 2Al<sub>2</sub>O<sub>3</sub>    (<i>correct</i>)                          (6)37                                        C<sub>3</sub>H<sub>8</sub> + 5O<sub>2</sub> &rarr; 3CO<sub>2</sub> + 4H<sub>2</sub>O (correct)               (7)38</font>39</pre>40<p>41The coefficients of Equation (6) are (4, 3, 2) from left to right, and those of Equation (7) are42(1, 5, 3, 4) from left to right. Note that the coefficient 1 may be omitted from chemical equations.43</p>44 45<p>46The coefficients of a <i>correct</i> equation must satisfy the following conditions.47</p>48 49<ol>50<li> The coefficients are all positive integers.</li>51<li> The coefficients are relatively prime, that is, their greatest common divisor (g.c.d.) is 1.</li>52<li> The quantities of each chemical element on the left-hand side and the right-hand side are53   equal.</li>54</ol>55 56<p>57Conversely, if a chemical equation satisfies the above three conditions, we regard it as a correct58equation, no matter whether the reaction or its constituent molecules can be chemically realized59in the real world, and no matter whether it can be called a reaction (e.g., H<sub>2</sub> &rarr; H<sub>2</sub> is considered60correct). A chemical equation satisfying Conditions 1 and 3 (but not necessarily Condition 2)61is called a <i>balanced</i> equation.62</p>63 64<p>65Your goal is to read in chemical equations with missing coefficients like Equation (4) and (5),66line by line, and output the sequences of coefficients that make the equations correct.67</p>68 69<p>70Note that the above three conditions do not guarantee that a correct equation is uniquely71determined. For example, if we "mix" the reactions generating H<sub>2</sub>O and NH<sub>3</sub> , we would get72</p>73 74<pre><font face="Times New Roman">75<i>x</i>H<sub>2</sub> + <i>y</i>O<sub>2</sub> + <i>z</i>N<sub>2</sub> + <i>u</i>H<sub>2</sub> &rarr; <i>v</i>H<sub>2</sub>O + <i>w</i>NH<sub>3</sub>     (8)76</font></pre>77 78<p>79but (<i>x</i>, <i>y</i>, <i>z</i>, <i>u</i>, <i>v</i>, <i>w</i>) = (2, 1, 1, 3, 2, 2) does not represent a unique correct equation; for instance,80(4, 2, 1, 3, 4, 2) and (4, 2, 3, 9, 4, 6) are also "correct" according to the above definition! However,81we guarantee that every chemical equation we give you will lead to a <i>unique</i> correct equation by82adjusting their coefficients. In other words, we guarantee that (i) every chemical equation can be83balanced with positive coefficients, and that (ii) <i>all</i> balanced equations of the original equation84can be obtained by multiplying the coefficients of a unique correct equation by a positive integer.85 86</p>87 88<H2>Input</H2>89 90<p>91The input is a sequence of chemical equations (without coefficients) of the following syntax in92the Backus-Naur Form:93</p>94 95<pre>96&lt;chemical_equation&gt; ::= &lt;molecule_sequence&gt; "-&gt;" &lt;molecule_sequence&gt;97&lt;molecule_sequence&gt; ::= &lt;molecule&gt; | &lt;molecule&gt; "+" &lt;molecule_sequence&gt;98         &lt;molecule&gt; ::= &lt;group&gt; | &lt;group&gt; &lt;molecule&gt;99            &lt;group&gt; ::= &lt;unit_group&gt; | &lt;unit_group&gt; &lt;number&gt;100       &lt;unit_group&gt; ::= &lt;chemical_element&gt; | "(" &lt;molecule&gt; ")"101 &lt;chemical_element&gt; ::= &lt;uppercase_letter&gt;102                      | &lt;uppercase_letter&gt; &lt;lowercase_letter&gt;103 &lt;uppercase_letter&gt; ::= "A" | "B" | "C" | "D" | "E" | "F" | "G" | "H" | "I"104                      | "J" | "K" | "L" | "M" | "N" | "O" | "P" | "Q" | "R"105                      | "S" | "T" | "U" | "V" | "W" | "X" | "Y" | "Z"106 &lt;lowercase_letter&gt; ::= "a" | "b" | "c" | "d" | "e" | "f" | "g" | "h" | "i"107                      | "j" | "k" | "l" | "m" | "n" | "o" | "p" | "q" | "r"108                      | "s" | "t" | "u" | "v" | "w" | "x" | "y" | "z"109           &lt;number&gt; ::= &lt;non_zero_digit&gt;110                      | &lt;non_zero_digit&gt; &lt;digit&gt;111   &lt;non_zero_digit&gt; ::= "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" |112            &lt;digit&gt; ::= "0" | &lt;non_zero_digit&gt;113</pre>114 115<p>116Each chemical equation is followed by a period and a newline. No other characters such as117spaces do not appear in the input. For instance, the equation118</p>119 120<pre>121<font face="Times New Roman">122C<sub>a</sub>(OH)<sub>2</sub> + CO<sub>2</sub> &rarr; C<sub>a</sub>CO<sub>3</sub> + H<sub>2</sub>O123</font></pre>124<p>125is represented as126</p>127 128<pre>129Ca(OH)2+CO2->CaCO3+H2O.130</pre>131 132<p>133Each chemical equation is no more than 80 characters long, and as the above syntax implies,134the &lt;number&gt;'s are less than 100. Parentheses may be used but will not be nested (maybe a135good news to some of you!). Each side of a chemical equation consists of no more than 10136top-level molecules. The coefficients that make the equations correct will not exceed 40000. The137chemical equations in the input have been chosen so that 32-bit integer arithmetic would suffice138with appropriate precautions against possible arithmetic overflow. You are free to use 64-bit139arithmetic, however.140</p>141 142<p>143The end of the input is indicated by a line consisting of a single period.144</p>145 146<p>147Note that our definition of &lt;chemical_element&gt; above allows chemical elements that do not148exist or unknown as of now, and excludes known chemical elements with three-letter names (e.g.,149ununbium (Uub), with the atomic number 112).150</p>151 152<H2>Output</H2>153 154<p>155For each chemical equation, output a line containing the sequence of positive integer coefficients156that make the chemical equation <i>correct</i>. Numbers in a line must be separated by a single space.157No extra characters should appear in the output.158</p>159 160<H2>Sample Input</H2>161<pre>162N2+H2->NH3.163Na+Cl2->NaCl.164Ca(OH)2+CO2->CaCO3+H2O.165CaCl2+AgNO3->Ca(NO3)2+AgCl.166C2H5OH+O2->CO2+H2O.167C4H10+O2->CO2+H2O.168A12B23+C34D45+ABCD->A6D7+B8C9.169A98B+B98C+C98->A98B99C99.170A2+B3+C5+D7+E11+F13->ABCDEF.171.172</pre>173 174<H2>Output for the Sample Input</H2>175<pre>1761 3 21772 1 21781 1 1 11791 2 1 21801 3 2 31812 13 8 101822 123 33042 5511 41361831 1 1 118415015 10010 6006 4290 2730 2310 30030185</pre>186