QOJ.ac

QOJ

Süre Sınırı: 3 s Bellek Sınırı: 2048 MB Toplam puan: 100

#8852. 自組裝

İstatistikler

Automatic Chemical Manufacturing 正在試驗一種稱為自組裝的過程。在這個過程中,彼此具有天然親和力的分子混合在溶液中,讓它們自發組裝成更大的結構。但有個問題:分子有時會組裝成大小無上限的結構,導致機器堵塞。

你必須撰寫程式,判斷給定的一組分子是否能組裝成大小無上限的結構。你應採用兩個簡化假設:1)問題僅限於二維;2)集合中的每個分子都表示為正方形。正方形的四條邊代表該分子可以與其他相容分子連接的表面。

每筆測試資料會給你一組分子描述。每種類型的分子以四個由兩個字元組成的連接標籤描述,指出它的邊如何與其他分子的邊連接。連接標籤有兩種:

  • 一個大寫字母(A、……、Z),後面接著 + 或 -。若兩條邊的標籤具有相同的字母但不同的符號,則它們相容。例如,A+ 與 A- 相容,但與 A+ 或 B- 不相容。

  • 兩個數字零 00。具有這種標籤的邊與任何邊都不相容(即使是另一條標為 00 的邊也不相容)。

假設每種類型的分子都有無限供應,且分子可以旋轉與鏡射。當分子組裝成更大的結構時,兩個分子的邊只有在相容時才能彼此相鄰。無論連接標籤為何,任何邊都可以不連接任何東西(即該邊沒有相鄰分子)。

圖 A.1 展示三種分子,以及可由它們組裝出的一個大小有上限的結構(這組分子也能組成其他大小有上限的結構)。

problem_8852_149f15990c8350b340b82ed53cd8ac58.png

圖 A.1:範例輸入 1 的示意圖。

輸入格式

輸入僅包含一筆測試資料。每筆測試資料有兩行。第一行包含一個整數 $n$($1 \le n \le 40\,000$),表示分子類型的數量。第二行包含 $n$ 個長度為八個字元的字串,每個字串描述一種分子,字串之間以一個空格分隔。每個字串包含四個由兩個字元組成的連接標籤,按順時針順序代表分子的四條邊。

輸出格式

若這些類型的分子能產生大小無上限的結構,輸出單字 unbounded。否則,輸出單字 bounded。

範例

輸入格式 1

3
A+00A+A+ 00B+D+A- B-C+00C+

輸出格式 1

bounded

輸入格式 2

1
K+K-Q+Q-

輸出格式 2

unbounded

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.