2017 Atlantic Canadian Preliminary Contest


2017-10-13 15:30 UTC

2017 Atlantic Canadian Preliminary Contest


2017-10-13 20:30 UTC
The end is near!
Contest is over.
Not yet started.
Contest is starting in -559 days 0:23:26

Time elapsed


Time remaining


Problem D

Image by kabliczech (iStock), Used under license

One of the most fundamental structures in abstract algebra is called a magma. A magma is a pair $(M,\bullet )$, where $M$ is a nonempty set and $\bullet $ is a binary operation on $M$. This means that $\bullet $ maps each ordered pair of elements $(x,y)$ in $M$ to an element in $M$ (in other words, $\bullet $ is a function from $M \times M$ to $M$). The element to which $\bullet $ maps $(x,y)$ is denoted $x \bullet y$.

Magmas that satisfy certain properties are given more specialized names. Here are three important properties that $(M,\bullet )$ could satisfy:

  • P1 (associativity): For all $x,y,z \in M$, $(x \bullet y) \bullet z = x \bullet (y \bullet z)$.

  • P2 (identity): There is an element $I \in M$ such that $x \bullet I = I \bullet x = x$ for all $x \in M$ ($I$ is called an identity).

  • P3 [depends on P2] (inverses): There is an identity $I \in M$, and for every $x \in M$, there exists $x^* \in M$ such that $x \bullet x^* = x^* \bullet x = I$ ($x^*$ is called an inverse of $x$).

A magma that satisfies P1 is called a semigroup. A semigroup that satisfies P2 is called a monoid. A monoid that satisfies P3 is called a group. Given a magma $(M,\bullet )$, determine its most specialized name.


The input consists of a single test case specifying a magma $(M,\bullet )$. The first line contains an integer $n$ $(1 \leq n \leq 120)$, the size of $M$. Assume that the elements of $M$ are indexed $0,1,2,\ldots ,n-1$. Each of the next $n^2$ lines contains three integers $i~ j~ k$ $(0 \leq i,j,k \leq n-1)$, meaning that $x \bullet y = z$, where $x$ is the element indexed by $i$, $y$ is the element indexed by $j$, and $z$ is the element indexed by $k$. Each ordered pair $(i,j)$ will appear exactly once as the first two values on a line.


The output consists of a single line. Output group if $(M,\bullet )$ satisfies P1, P2, and P3. Output monoid if $(M,\bullet )$ satisfies P1 and P2, but not P3. Output semigroup if $(M,\bullet )$ satisfies P1, but not P2 (and therefore not P3). Otherwise, output magma.

Sample Input 1 Sample Output 1
0 0 0
0 1 1
1 0 1
1 1 0
Sample Input 2 Sample Output 2
1 2 1
2 0 0
0 1 0
2 2 2
1 0 0
0 0 0
2 1 1
0 2 0
1 1 2