Chương trình tiền sử
Đề bài
Mô tả
Các nhà khảo cổ vừa phát hiện những tấm bảng đất sét thú vị trong các tầng sâu của hang Alutila. Không ai giải mã được chữ viết trên các tấm bảng, ngoại trừ hai ký hiệu dường như mô tả các cấu trúc lồng nhau, không khác mấy so với dấu ngoặc mở và dấu ngoặc đóng trong LISP. Phải chăng con người đã viết chương trình từ hàng nghìn năm trước?
Gộp lại với nhau, các tấm bảng có vẻ mô tả một tác phẩm vĩ đại: có thể là một chương trình, một bản sử thi, hoặc thậm chí là sổ thuế! Chẳng có gì ngạc nhiên khi sau một thời gian dài như vậy, các tấm bảng đã bị xáo trộn. Nhiệm vụ của bạn là sắp xếp chúng thành một dãy sao cho tác phẩm thu được có cấu trúc ngoặc lồng nhau đúng. Chỉ xét các dấu ngoặc mở và đóng, một cấu trúc lồng nhau đúng là
(), hoặc(A), trong đó là một cấu trúc lồng nhau đúng, hoặc- , trong đó và là các cấu trúc lồng nhau đúng.
Dữ liệu vào
Dòng đầu tiên chứa một số nguyên (): số tấm bảng.
Mỗi dòng trong dòng tiếp theo mô tả một tấm bảng, gồm một xâu khác rỗng chỉ chứa các dấu ngoặc mở ( và ngoặc đóng ); các ký hiệu không liên quan tới cấu trúc lồng nhau đã được bỏ đi. Các xâu được đánh số từ tới theo thứ tự xuất hiện trong dữ liệu vào. Tổng số dấu ngoặc trong dữ liệu vào không quá .
Dữ liệu ra
In ra một hoán vị của các số từ tới , mỗi số trên một dòng, sao cho khi ghép các xâu theo thứ tự này ta được một cấu trúc lồng nhau đúng. Nếu có nhiều hoán vị thỏa mãn, in ra hoán vị nào cũng được chấp nhận. Nếu không có hoán vị nào như vậy, in ra impossible.
Ràng buộc
- .
- Mỗi xâu khác rỗng, chỉ gồm các ký tự
(và). - Tổng độ dài các xâu không quá .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 2 ())())() ((() |
2 1 |
Ghép xâu 2 rồi xâu 1 được ((()())())(), là cấu trúc lồng nhau đúng. |
| 5 ( )) (( )) ( |
1 5 3 2 4 |
Ghép theo thứ tự 1, 5, 3, 2, 4 được (((()))). Các thứ tự khác như 1, 3, 5, 2, 4 cũng được chấp nhận. |
| 2 (( ) |
impossible | Tổng cộng có dấu ngoặc mở nhưng chỉ có dấu ngoặc đóng, nên không thứ tự nào cho cấu trúc đúng. |
Bình luận