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.