Tên tác giả
Đề bài
Mô tả
Người ta thường sắp danh sách tác giả của một bài báo theo thứ tự từ điển. Tuy nhiên, thứ tự từ điển ở đây không nhất thiết dựa trên bảng chữ cái Latin thông thường, mà dựa trên một thứ tự nào đó của chữ cái.
Cho một danh sách gồm cái tên (theo đúng thứ tự chúng xuất hiện). Hãy xác định xem có tồn tại một cách sắp xếp lại thứ tự của chữ cái trong bảng chữ cái (một hoán vị của 'a'..'z') sao cho danh sách các tên đã cho được sắp theo đúng thứ tự từ điển hay không. Nếu có, in ra một thứ tự bảng chữ cái bất kỳ thoả mãn.
Thứ tự từ điển được định nghĩa như sau: khi so sánh hai xâu và , ta tìm vị trí đầu tiên khác nhau . Nếu không có vị trí như vậy (tức một xâu là tiền tố của xâu kia) thì xâu ngắn hơn được coi là nhỏ hơn. Ngược lại, ta so sánh và theo thứ tự của chúng trong bảng chữ cái.
Dữ liệu vào
- Dòng đầu chứa số nguyên : số lượng tên.
- dòng tiếp theo, mỗi dòng chứa một xâu chỉ gồm các chữ cái Latin thường. Tất cả các tên đều khác nhau.
Dữ liệu ra
Nếu tồn tại một thứ tự bảng chữ cái sao cho các tên đã cho được sắp theo thứ tự từ điển, in ra thứ tự đó dưới dạng một hoán vị của các chữ cái 'a'..'z' (đầu tiên là chữ cái đứng đầu bảng chữ cái mới, rồi đến chữ cái thứ hai, và cứ thế).
Ngược lại, in ra một dòng duy nhất chứa từ "Impossible" (không có dấu ngoặc kép).
Nếu có nhiều đáp án, in ra bất kỳ đáp án nào.
Ràng buộc
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 3 rivest shamir adleman |
bcdefghijklmnopqrsatuvwxyz | Với thứ tự bảng chữ cái này, 'r' đứng trước 's', và 's' đứng trước 'a', nên rivest < shamir < adleman. Bất kỳ hoán vị hợp lệ nào khác cũng được chấp nhận. |
| 10 tourist petr wjmzbmr yeputons vepifanov scottwu oooooooooooooooo subscriber rowdark tankengineer |
Impossible | Không tồn tại thứ tự bảng chữ cái nào khiến danh sách này được sắp đúng thứ tự từ điển. |
| 2 aa a |
Impossible | "a" là tiền tố của "aa" nên "a" phải đứng trước "aa"; nhưng ở đây "aa" lại đứng trước, mâu thuẫn với mọi thứ tự bảng chữ cái. |
Bình luận