問題一覧 > 通常問題

No.2820 Non-Preferred IUPAC Nomenclature

レベル : / AI推定難易度 : 925 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 72
作問者 : みどりむし🦠 / テスター : achapi FplusFplusF viral8 👑 AngrySadEight
お気に入りにしたユーザー ProblemId : 10799 / 自分の提出
問題文最終更新日: 2024-07-27 19:43:04
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 438 (順位表) の他の問題:

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 ane from the end of its name, then attaching ( to the beginning and yl) to the end.
    • The name is the string obtained by appending methane to 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.

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 H appears more than once
    • The hydrocarbon consisting of these carbon atoms is an alkane
(Wording revised after the contest)

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

By entering a name on this page, you can draw a schematic diagram of the alkane that has that name. (This is an external site.)

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もしくは右上の雲マークをクリックしてアカウントを作成してください。