Problem #3433 - ECNU Online Judge

单点时限: 1.0 sec

内存限制: 256 MB

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:

$C H_{4} + 2 O_{2} \to C O_{2} + 2 H_{2} O$

which can be read as: “One molecule of $C H_{4}$ and two molecules of $O_{2}$ yield one molecule of $C O_{2}$ and two molecules of $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:

$\rm{_ H_2 O + _ C O_2 \rightarrow _ O_2 + _ C_6 H_{12} O_6}$

will fill in the blanks to produce a balanced equation. For example, the above equation could be balanced as follows:

$6 H_{2} O + 6 C O_{2} \to 6 O_{2} + 1 C_{6} H_{12} O_{6} .$

输入格式

An equation is input in the form of a sequence of $M$ $(1 < M \leq 20)$ lines, one for each molecule in the formula (e.g., $H_{2} O$ or $C O_{2}$ ). Each line $m$ ( $1 \leq m \leq M$ ) has the following fields:

$s i g n_{m} N_{m} e l e m e n t_{m, 1} c o u n t_{m, 1} \dots e l e m e n t_{m, N_{m}} c o u n t_{m, N_{m}}$

where $s i g n_{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 $e l e m e n t$ / $c o u n t$ pairs following on the line. Each $e l e m e n t_{m, n}$ , where $1 \leq n \leq N_{m}$ , is an element name consisting of one or two upper or lowercase letters, and each $c o u n t_{m, n}$ is a positive integer, $1 \leq c o u n t_{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 $C H_{5} C O O H$ appears on the left side of the equation. Note that $C H_{5} C O O H$ can be written as $C_{2} H_{6} O_{2}$ .

Input ends with a line of the form 0 0.

输出格式

The program must output the numbers $C_{1}, \dots, C_{M}$ $(0 < C_{i} \leq 1 000)$ , in order, to fill in the blanks in the equation. Each number, $C_{m} ∣ 1 \leq m \leq 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.

样例

Input

+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

Output

6 6 6 1

Input

+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

Output

2 6 1 5 2

2 人解决，2 人已尝试。

2 份提交通过，共有 10 份提交。

8.4 EMB 奖励。

创建: 7 年，4 月前.

修改: 7 年，4 月前.

最后提交: 4 年，4 月前.

来源: NCNA 2017

matrix

3433. Stoichiometry

输入格式

输出格式

样例

服务

开源

关于我们