Hình dưới là cơ cấu của một đường tàu tại một ga xe lửa:
Ban
đầu ở đường ray A có chứa các toa tàu được đánh số thứ tự từ 1 đến n theo thứ tự
từ trái qua phải, người ta muốn chuyển các toa đó sang ray C để có được một thứ
tự mới là một hoán vị của (1, 2, …, n) theo quy tắc: chỉ chứa được các toa tàu
chạy theo đường ray theo hướng mũi tên, có thể dùng đường ray B để lưu tạm các
toa tàu trong quá trình di chuyển.
Cho
biết hoán vị cần có, hãy tìm phương án di chuyển ít nhất các toa tàu trên đường
ray.
Dữ
liệu vào:
-
Dòng 1: Một số nguyên dương n (n <= 105).
-
Dòng 2: n số nguyên là hoán vị của các số
từ 1 đến n.
Dữ
liệu ra:
-
Nếu không có phương án thì đưa ra thông báo là
NO
-
Nếu có phương án thì:
+
Dòng 1 đưa ra thông báo YES
+
Các dòng tiếp theo đưa ra các bước di chuyển ít nhất các toa tàu.
Ví dụ:
|
Input |
Output |
|
4 1 4 3 2 |
YES A->C A->B A->B A->C B->C B->C |
Đăng nhận xét