Tháp Hà Nội

Điểm: 1,00 (OI)

Giới hạn thời gian: 1.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Có ba cọc (đánh số 1, 2, 3) và $n$ chiếc đĩa có kích thước khác nhau. Ban đầu, tất cả các đĩa được xếp trên cọc 1 theo thứ tự từ lớn đến nhỏ (đĩa lớn ở dưới, đĩa nhỏ ở trên). Mục tiêu là chuyển toàn bộ đĩa sang cọc 3.

Quy tắc:

Mỗi lần chỉ được di chuyển một đĩa (đĩa trên cùng của một cọc).
Không được đặt đĩa lớn lên trên đĩa nhỏ hơn.

Hãy tìm cách di chuyển với số bước ít nhất.

Dữ liệu vào

Một dòng duy nhất chứa số nguyên $n$ .

Dữ liệu ra

Dòng đầu tiên in ra $k$ — số bước di chuyển tối thiểu.

$k$ dòng tiếp theo, mỗi dòng gồm hai số nguyên $a$ và $b$ : di chuyển đĩa trên cùng từ cọc $a$ sang cọc $b$ .

Ràng buộc

$1 \leq n \leq 16$

Ví dụ

Input	Output	Giải thích
2	3 1 2 1 3 2 3	Cần 3 bước: cọc 1→2, cọc 1→3, cọc 2→3.
1	1 1 3	Chỉ cần 1 bước.

Bình luận

Không có bình luận tại thời điểm này.