Minh họa Tháp Hà Nội
Có 3 cọc A, B, C. Cọc A có n đĩa to nhỏ khác nhau, đĩa to ở dưới. Cần chuyển cả n đĩa sang cọc C, mỗi lần chuyển một đĩa trên cùng của một cọc sang cọc khác, và không bao giờ đặt đĩa to lên đĩa nhỏ. Hãy in cách chuyển với số lần ít nhất.
Dữ liệu vào
Một số nguyên n.
Kết quả
Dòng đầu là số lần chuyển. Mỗi dòng tiếp theo có dạng "X Y" nghĩa là chuyển đĩa trên cùng từ cọc X sang cọc Y.
Giới hạn
1 ≤ n ≤ 12.
Ví dụ 1 – vào
2
Ví dụ 1 – ra
3 A B A C B C
Ví dụ 2 – vào
3
Ví dụ 2 – ra
7 A C A B C B A C B A B C A C