Mock CCC '21 S4 - Infinite Molecule

View as PDF

Submit solution

Points: 12 (partial)
Time limit: 0.25s
Memory limit: 1G

Problem type

You have a chemistry model of N types of atoms where each type of atom is approximated by a unit square, where each side of the square has a label on it. Atoms can be connected if and only if they share a side fully - furthermore, the two labels of the shared side must be nonzero and sum to zero. Clearly, an atom can be connected to at most four other atoms. Atoms may be rotated or reflected.

Is it possible to build an infinitely large molecule out of these atoms? Assume you have infinitely many of every type of atom.


1 \le N \le 4 \cdot 10^4

Each label has absolute value at most 26.

Input Specification

The first line contains a single integer N.

The next N lines each contain four space-separated integers - the four labels in clockwise order of the sides of the square.

Output Specification

If it is possible to build an infinite large molecule, print 1. Otherwise, print 0.

Sample Input

1 -1 2 -2

Sample Output



There are no comments at the moment.