DMOPC '19 Contest 7 P1 - Hydrocarbons - DMOJ: Modern Online Judge

DMOPC '19 Contest 7 P1 - Hydrocarbons

Points: 7

Time limit: 2.0s

Memory limit: 256M

Author:

Problem type

Veshy is struggling in chemistry so he asks you for help in naming hydrocarbons. As you know from chemistry, hydrocarbons are organic compounds consisting only of carbon and hydrogen atoms bonded covalently.

Covalent bonds in hydrocarbons can be either carbon-carbon single bonds (C $-$ $-$ C), carbon-carbon double bonds (C $=$ $=$ C), carbon-carbon triple bonds (C $\equiv$ $\equiv$ C), or carbon-hydrogen bonds (C $-$ $-$ H). Following the bonding rules, each carbon atom must have exactly four covalent bonds, and each hydrogen atom must have exactly one covalent bond for the molecule to be valid. As well, there must be one unique chain of bonds between any two atoms in the hydrocarbon; in other words, the structure must be acyclic.

Given $a$ $a$ carbon-carbon single bonds, $b$ $b$ carbon-carbon double bonds, $c$ $c$ carbon-carbon triple bonds, and $d$ $d$ carbon-hydrogen bonds, determine the formula of the hydrocarbon in terms of $\text{C}_n\text{H}_m$ $C_{n} H_{m}$ ( $n$ $n$ and $m$ $m$ are positive integers) if you can form a valid hydrocarbon (all carbon and hydrogen atoms have the correct number of bonds) using all the given bonds. If a valid hydrocarbon cannot be formed output invalid.

Input Specification

The only line of input will contain four space-separated integers, $a, b, c, d$ $a, b, c, d$ $(0 \le a,b,c,d \le 1500)$ $(0 \leq a, b, c, d \leq 1500)$ .

Output Specification

There is only one line in the output.
If a valid hydrocarbon can be formed, output the chemical formula of the hydrocarbon in the form CnHm, where $n$ $n$ and $m$ $m$ are the positive integers denoting the number of carbon and hydrogen atoms in the hydrocarbon respectively.

Sample Input 1

Copy

0 0 0 4

Sample Output 1

Copy

C1H4

Sample Input 2

Copy

1 0 0 3

Sample Output 2

Copy

invalid

Sample Input 3

Copy

1 0 0 6

Sample Output 3

Copy

C2H6

Explanation

In Sample 1, there are four carbon-hydrogen bonds which fills all required bonds:

$\text{[math]}$

In Sample 2, it is impossible to satisfy the number of covalent bonds required by the carbon atoms.
In Sample 3, each carbon atom is bonded to one other carbon atom and three other hydrogen atoms:

$\text{[math]}$

Comments

1

Narcariel commented on Jan. 20, 2021, 3:34 p.m.

Why is this graph theory, shouldn't it just be implementation.

2

Narcariel commented on May 7, 2020, 2:31 p.m.

How are there comments on an editorial when there isn't one?

1

Tzak commented on May 7, 2020, 5:44 p.m.

The test data for P1 was weak, which allowed many wrong solutions like the editorial solution to pass. We're working on a new editorial (and maybe some better test data?).

1

ross_cleary commented on May 7, 2020, 5:58 p.m.

What is an example of a case that would fail many solutions?

8
Tzak commented on May 7, 2020, 7:26 p.m.
Input:

Copy
0 1 1 2

Expected Output:

Copy
invalid