Elearning CodePath – CTP Online Judge

Những Cánh Cửa Bí Mật (Secret Doors)

DOORS

🟢 Easy #Graph

📌 Thông tin chung
Tên File Input	DOORS.INP
Tên File Output	DOORS.OUT

📝 Đề bài

Tại một địa điểm khảo cổ, nhóm nghiên cứu phát hiện ra những cánh cửa bí mật chứa các câu đố chữ thú vị. Trên mỗi cánh cửa có rất nhiều tấm thẻ từ tính, mỗi tấm thẻ ghi một từ tiếng Anh duy nhất. Để mở được cửa, nhóm khảo cổ phải sắp xếp tất cả các tấm thẻ này thành một dãy sao cho chữ cái bắt đầu của một từ phải trùng với chữ cái kết thúc của từ đứng ngay trước nó.

Ví dụ: Từ 'acm' có thể được theo sau bởi từ 'motorola' vì 'acm' kết thúc bằng 'm' và 'motorola' bắt đầu bằng 'm'.

Nhiệm vụ của bạn là viết một chương trình đọc danh sách các từ và xác định xem có thể sắp xếp tất cả các tấm thẻ thành một dãy thỏa mãn quy tắc trên hay không.

Định dạng Đầu vào:
- Dòng đầu tiên chứa số nguyên T là số lượng bộ test.
- Mỗi bộ test bắt đầu bằng số nguyên N (1 <= N <= 100000) là số lượng tấm thẻ.
- N dòng tiếp theo, mỗi dòng chứa một từ (độ dài từ 2 đến 1000 ký tự, chỉ gồm chữ cái 'a'-'z').
- Một từ có thể xuất hiện nhiều lần trong danh sách.

Định dạng Đầu ra:
- Với mỗi bộ test, nếu có thể sắp xếp tất cả các tấm thẻ thành một dãy, in ra: Ordering is possible.
- Ngược lại, in ra: The door cannot be opened.

Ví dụ:
Input:
3
2
acm
ibm
3
acm
malform
mouse
2
ok
ok

Output:
The door cannot be opened.
Ordering is possible.
The door cannot be opened.

Subtask:
- Subtask 1 (30% số điểm): N <= 10.
- Subtask 2 (70% số điểm): N <= 100000.

✅ Đã AC: 7 / 33 submissions