Tự lắp ráp
Đề bài
Mô tả
Công ty Automatic Chemical Manufacturing đang thử nghiệm một quy trình gọi là tự lắp ráp. Trong quy trình này, các phân tử có ái lực tự nhiên với nhau được trộn chung trong một dung dịch và để chúng tự kết nối thành những cấu trúc lớn hơn. Nhưng có một vấn đề: đôi khi các phân tử tự lắp ráp thành một cấu trúc có kích thước không bị chặn, làm kẹt cả dây chuyền máy móc.
Bạn cần viết chương trình xác định xem một tập phân tử cho trước có thể lắp ráp thành một cấu trúc có kích thước không bị chặn hay không. Ta dùng hai giả thiết đơn giản hóa: 1) bài toán chỉ xét trong mặt phẳng hai chiều, và 2) mỗi phân tử được biểu diễn bằng một hình vuông. Bốn cạnh của hình vuông là các mặt mà phân tử có thể kết nối với các phân tử tương thích khác.
Mỗi test cho một tập các loại phân tử. Mỗi loại phân tử được mô tả bởi bốn nhãn đầu nối, mỗi nhãn gồm hai ký tự, cho biết các cạnh của nó có thể nối với cạnh của phân tử khác như thế nào. Có hai kiểu nhãn đầu nối:
- Một chữ cái in hoa (
A, ...,Z) theo sau bởi+hoặc-. Hai cạnh tương thích nếu nhãn của chúng có cùng chữ cái nhưng khác dấu. Ví dụ,A+tương thích vớiA-nhưng không tương thích vớiA+hayB-. - Hai chữ số không
00. Cạnh mang nhãn này không tương thích với bất kỳ cạnh nào (kể cả một cạnh khác cũng mang nhãn00).
Giả sử mỗi loại phân tử có số lượng không giới hạn, và các phân tử có thể được xoay và lật (lấy đối xứng). Khi các phân tử tự lắp ráp thành cấu trúc lớn hơn, cạnh của hai phân tử chỉ được nằm kề nhau nếu chúng tương thích. Một cạnh, bất kể nhãn là gì, được phép không nối với gì cả (không có phân tử nào kề với cạnh đó).
Hình dưới minh họa ví dụ thứ nhất: bên trái là ba loại phân tử, bên phải là một cấu trúc có kích thước bị chặn lắp ráp được từ chúng (với tập phân tử này còn có những cấu trúc bị chặn khác).

Dữ liệu vào
Dữ liệu gồm một test duy nhất, nằm trên hai dòng. Dòng đầu tiên chứa số nguyên , số loại phân tử. Dòng thứ hai chứa xâu, mỗi xâu dài đúng ký tự mô tả một loại phân tử, các xâu cách nhau đúng một dấu cách. Mỗi xâu gồm bốn nhãn đầu nối (mỗi nhãn hai ký tự) của bốn cạnh của phân tử, theo thứ tự chiều kim đồng hồ.
Dữ liệu ra
In ra unbounded nếu tập các loại phân tử có thể tạo ra một cấu trúc có kích thước không bị chặn. Ngược lại, in ra bounded.
Ràng buộc
- .
- Mỗi nhãn là
00hoặc một chữ cái in hoa theo sau bởi+hoặc-.
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 3 A+00A+A+ 00B+D+A- B-C+00C+ |
bounded | Ba loại phân tử như trong hình. Mọi cấu trúc lắp ráp được đều có kích thước bị chặn. |
| 1 K+K-Q+Q- |
unbounded | Cạnh K+ của một phân tử nối được với cạnh K- của một bản sao khác của chính nó, nên có thể xếp một hàng phân tử dài tùy ý. |
Bình luận