COCI '21 Contest 5 #1 Kemija

View as PDF

Submit solution


Points: 7 (partial)
Time limit: 1.0s
Memory limit: 512M

Problem type

Fran didn't pay attention in school during chemistry class and now he needs your help in doing his homework. His homework consists of n chemical equations for which he needs to check if they are balanced. A chemical equation is a way of representing chemical reactions using symbols and formulas. In a chemical reaction, some set of initial molecules react to produce a new set of molecules.

A chemical equation has a left side and a right side. The left side contains chemical formulas of the initial molecules, while the right side contains chemical formulas of the product molecules. The left and the right sides of the equation are separated by an arrow (characters ->). Different molecules appearing on the left or the right side are separated by a +.

Molecules are substances made from atoms, tiny particles which are denoted with capital letters of the Latin alphabet (for the purposes of this task). The formula of a molecule is written by listing the labels of all the different atoms which make up the molecule. If a molecule has multiple instances of some atom, then the number of occurrences of this atom is written after the atom in the formula. For example, AC4B is a formula for a molecule which has one atom A, 4 atoms C and one atom B. If on one side of the equation a molecule appears more than once, then this number of occurrences is written as a coefficient in front of the formula. For example, 3AC4B denotes 3 molecules of AC4B, for a total of 3 atoms A, 12 atoms C and 3 atoms B.

A chemical equation is said to be balanced if the right side and the left side contain an equal number of atoms of each kind. Your task is to determine whether or not each of the n chemical equations is balanced. The test cases will be such that all the numbers appearing in the reactions (the numbers of atoms in molecules and the numbers of molecules in the reactions) will have only a single digit (and they will be larger than 1).

Input Specification

The first line contains a positive integer n (1 \le n \le 10), the number of chemical equations. Each of the next n lines contains a sequence of characters representing a chemical equation.

Each equation consists of at most 1\,000 characters. The equations will not necessarily be balanced, but they will be correctly written as described in the statement.

Output Specification

For each of the n equations print DA if it is balanced, and NE if it is not, in separate lines.

Constraints

Subtask Points Constraints
1 10 No chemical reaction has a number in it.
2 10 No numbers appear within any formulas for molecules.
3 30 No additional constraints.

Sample Input 1

3
A+B->AB
AB+CD->AC+DB
AB+B->AB

Sample Output 1

DA
DA
NE

Sample Input 2

2
2AB+A->3AB
2AB+2AC+2BC->4ABC

Sample Output 2

NE
DA

Sample Input 3

4
2H2O+2CO2->2H2CO3
H2SO4->H2O4
NH3+H2SO4->NH4SO4
CH4+2O2->CO2+2H2O

Sample Output 3

DA
NE
NE
DA

Explanation for Sample Output 3

First equation: both sides have 4 atoms H, 2 atoms C and 6 atoms O so the answer is DA.

Second equation: the left side has a single S atom, but the right side has none so the answer is NE.

Third equation: the left side has 5 atoms H, but the right side has 4 so the answer is NE.

Forth equation: both sides have 4 atoms H, one atom C and 4 atoms O so the answer is DA.


Comments

There are no comments at the moment.