trang chủ / đề bài / icpcwf13_a

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ới A- nhưng không tương thích với A+ hay B-.
  • 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ãn 00).

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 n, số loại phân tử. Dòng thứ hai chứa n xâu, mỗi xâu dài đúng 8 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

  • 1≤n≤40000.
  • Mỗi nhãn là 00 hoặ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

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0