Bài toán Tháp Hà Nội
Points
25
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
recursion
Đề bài
Có $N$ chiếc đĩa kích thước khác nhau nằm ở cọc A, đĩa nhỏ hơn nằm trên đĩa lớn hơn. Cần chuyển toàn bộ $N$ đĩa sang cọc C bằng cách dùng cọc trung gian B, mỗi lần chỉ chuyển 1 đĩa và không được đặt đĩa lớn lên trên đĩa nhỏ. Hãy in ra tổng số bước và từng bước di chuyển theo định dạng X -> Y.
Dữ liệu vào
Một dòng duy nhất chứa số nguyên dương $N$.
Dữ liệu ra
Dòng đầu tiên in tổng số bước di chuyển ($2^N - 1$).
Các dòng tiếp theo mỗi dòng ghi một bước di chuyển dạng X -> Y.
Ví dụ
| Input | Output |
|---|---|
| 2 | 3\nA -> B\nA -> C\nB -> C |
| 1 | 1\nA -> C |
Giới hạn
$1 \le N \le 10$.
Community Discussion