No.2820 Non-Preferred IUPAC Nomenclature
タグ : / 解いたユーザー数 72
作問者 :
みどりむし🦠
/ テスター :
FplusFplusF
Problem Statement
Note: This problem is fiction. It differs greatly from modern chemistry.
A carbon atom can bond (directly) with at most $4$ carbon atoms other than itself.
Something formed by $1$ or more carbon atoms bonded to one another is called a hydrocarbon.
In addition, every hydrocarbon has a string that serves as its name and exactly $1$ carbon atom that serves as its root.
An alkane is a hydrocarbon constructed recursively by the following rule:
- For a set $S$ of at most $4$ distinct alkanes, in each of which the number of carbon atoms (directly) bonded to the root is less than $4$, the hydrocarbon obtained by bonding $1$ common carbon atom $X$ to the root of every alkane belonging to $S$
- Let $P$ be the multiset of strings obtained, for every alkane belonging to $S$, by removing
anefrom the end of its name, then attaching(to the beginning andyl)to the end. - The name is the string obtained by appending
methaneto the end of the string $p$, where $p$ is obtained by concatenating all the strings belonging to $P$ in any order. - The root newly becomes $X$.
- In particular, when $S = \emptyset$, it is the hydrocarbon consisting only of the carbon atom $X$, its name is
methane, and its root is $X$ itself.
- Let $P$ be the multiset of strings obtained, for every alkane belonging to $S$, by removing
Now, there is $1$ alkane consisting of $N$ distinct carbon atoms, carbon atoms $1, 2, \dots, N$.
Find the name of this alkane.
Depending on the construction procedure, there may be multiple possible names; output any $1$ of them.
Note that whether a carbon atom is a root cannot be distinguished visually.
Therefore, which carbon atom is the root is not given, and you may freely choose one.
Input
The input is given from Standard Input in the following format:
$N$
$C_{1, 1} \enspace C_{1, 2} \enspace C_{1, 3} \enspace C_{1, 4}$
$C_{2, 1} \enspace C_{2, 2} \enspace C_{2, 3} \enspace C_{2, 4}$
$\vdots$
$C_{N, 1} \enspace C_{N, 2} \enspace C_{N, 3} \enspace C_{N, 4}$
- Define the multiset $L_i \coloneqq \{\!\!\{\, C_{i, 1}, C_{i, 2}, C_{i, 3}, C_{i, 4} \,\}\!\!\} \scriptsize \; (1 \leq i \leq N)$.
- $2$ carbon atoms $i, j \scriptsize \; (i \not= j)$ are (directly) bonded to each other if and only if $i \in L_j$
and $\sout {j \in L_i}$holds. - Here, it is guaranteed that all of the following are satisfied:
- $C_{i, j} \in \{\, 1, 2, \dots, N,$
H$\,\} \scriptsize \; (1 \leq i \leq N \land 1 \leq j \leq 4)$ - $i \not\in L_i \scriptsize \; (1 \leq i \leq N)$
- $\textcolor{#FF0000} {i \in L_j \Leftrightarrow j \in L_i \scriptsize \; (1 \leq i, j \leq N)}$
- For $L_i \scriptsize \; (1 \leq i \leq N)$, no value other than
Happears more than once - The hydrocarbon consisting of these carbon atoms is an alkane
- $C_{i, j} \in \{\, 1, 2, \dots, N,$
Output
Output the answer to Standard Output on one line.
Constraints
- $1 \leq N \leq 2 \times 10^5$
- $N$ is an integer
- Exactly $1$ alkane consisting of all $N$ carbon atoms is given
Auxiliary Tool
Sample
Sample Input/Output 1
Input
2 2 H H H 1 H H H
Sample Output
(methyl)methane
It is not ethane.
Sample Input/Output 2
Input
3 2 H H H 1 3 H H 2 H H H
Sample Output
(methyl)(methyl)methane
((methyl)methyl)methane is also a correct answer.
Sample Input/Output 3
Input
6 2 3 4 5 1 H H H 1 H H H 1 H H H 1 6 H H 5 H H H
Sample Output
(((methyl)(methyl)(methyl)methyl)methyl)methane
Sample Input/Output 4
Input
14 2 H H H 1 3 H H 2 4 5 H 3 H H H 3 H 9 6 H 5 8 7 H H 6 H 11 H 6 H 5 10 12 H H 9 H H 8 14 H H 13 9 H H 12 H H H H 11 H H
Sample Output
((methyl)methyl)(((((methyl)methyl)(methyl)methyl)((methyl)((methyl)methyl)methyl)methyl)(methyl)methyl)methane
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。