DMOPC '14 Exam Time P3 - Chemistry Homework

View as PDF

Submit solution

Points: 10 (partial)
Time limit: 1.0s
Memory limit: 128M

Problem type

One day your chemistry teacher is very angry at you since you didn't do any of the assigned homework questions — but don't worry, it's not that you're a bad student, it's because she told you that doing homework is dangerous and since you spend all your time programming you were unable to understand her sarcasm.

As punishment, she gives you a stack of structural diagrams of various hydrocarbons. Your task is to calculate the total bond energy of all the hydrocarbons. She then decides that you should draw them as well, and so she gives you only a list of the bonds between all the atoms of all of the molecules, in no particular order. In addition to the total bond energy, you should also determine the number and type of atoms in the compound.

However, you quickly realize that by simply entering the given data you can determine the total bond energy and the number of atoms by writing a program that calculates it for you using the data below.

Average bond energies (kJ/mol):

C-H 413

C-C 346

C=C 615

Since all the compounds are hydrocarbons, the only atoms you should worry about are hydrogen and carbon. You also know that a hydrogen atom makes exactly one bond while a carbon atom makes exactly four bonds and you notice that there are only single and double bonds between the carbon atoms in the diagrams. If an atom has too many or not enough bonds it means that the compound cannot exist and so you should output Impossible.

Note: Impossible test cases are guaranteed to have another error other than carbon atoms having too many bonds. Assume there will be at least one Carbon and one Hydrogen.

Input Specification

The first line of input will consist of n (1 \le n \le 1\,000), the number of atoms in the compound.

The second line of input will consist of m (1 \le m \le 1\,000), the number of bonds in the compound.

The next m lines will consist of two integers, a and b (1 \le a < b \le n), which represent the bond between two atoms.

Output Specification

There should be two lines of output.

The first line should contain the value of the total bond energy.

The second line should contain the number of atoms in the following format: CxHy, where x and y (x, y \ge 1) are the number of carbon and hydrogen atoms respectively. If x or y are equal to one, omit the value; for example, C1H4 should be CH4.

Sample Input

1 2
1 3
1 4
1 5

Sample Output



  • -4
    pblpbl  commented on Feb. 27, 2020, 10:41 p.m. edited

    Can hydrogen bond with hydrogen? If so, what happens?

  • -1
    zxyl  commented on Aug. 22, 2018, 2:26 a.m. edit 2

    Does a double bond count as one bond or two when checking for the number of bonds of each atom?

    Edit: I guess they count as two (Would have been nice if this was clarified though).

  • 2
    LOLWHATOMGBBQ  commented on Jan. 31, 2015, 1:29 a.m.

    What do I output if y = 0?

    • 6
      Sentient  commented on Jan. 31, 2015, 4:06 a.m.

      It is guaranteed that there will be at least one Carbon and one Hydrogen. The problem statement has been updated to clarify this.

  • 1
    DennisQin  commented on Jan. 14, 2015, 12:27 a.m.

    • 1
      FatalEagle  commented on Jan. 14, 2015, 12:38 a.m.

      a and b (1 \le a < b \le n), which represent the bond between two atoms.

      They are just the indices of two atoms connected by a bond.

  • 8
    thorthugnasty  commented on Jan. 13, 2015, 8:53 p.m.

    How does one determine if there is a double bond? Does it state the same edge in the input twice?