C. HTOWER - Tháp Hà Nội

Bộ nhớ: 256 MiB Thời gian: 1000 ms Nhập/xuất từ luồng chuẩn
Kiểu bài: Thông thường Kiểu chấm: Trình chấm ngoài

Đề bài

Có ba cọc A, B, C và có n chiếc đĩa đánh số từ 1 đến n có kích thước tương ứng là 1, 2, \ldots, n . Trạng thái ban đầu cả n chiếc đĩa đều ở cọc A và đĩa to luôn ở dưới đĩa nhỏ.

Yêu cầu: Hãy chuyển các đĩa từ cọc A sang cọc C sử dụng cọc B làm cọc trung gian sao cho các đĩa nhỏ luôn nằm trên đĩa to.

Dữ liệu:

  • Một dòng duy nhất chứa số nguyên dương n\ (1 \le n \le 15) là số đĩa.

Kết quả:

  • Gồm nhiều dòng (không quá 2^{15} dòng), mỗi dòng là một thao tác chuyển dạng X -> Y tức là chuyển đĩa trên cùng ở cọc X đặt lên trên cùng ở cọc Y ( X, Y \in \{ A, B, C \} ).

Ví dụ:

Dữ liệu:

2

Kết quả:

A->B
A->C
B->C

Giải thích:

  • Chuyển đĩa 1 từ cọc A sang cọc B ;
  • Chuyển đĩa 2 từ cọc A sang cọc C ;
  • Chuyển đĩa 1 từ cọc B sang cọc C .