BÀI TẬP 5 [C++]: DI CHUYỂN TOA TÀU

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 <= 10⁵).

-         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