CSES - Tower of Hanoi | Tháp Hà Nội - LQDOJ: Le Quy Don Online Judge

CSES - Tower of Hanoi | Tháp Hà Nội

Tác giả:

letangphuquy , Flower_On_Stone , SPyofgame

Dạng bài

Điểm: 1200 (p) Thời gian: 1.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Trò chơi Tháp Hà Nội gồm có \(3\) ngăn xếp (số \(1\) bên trái, số \(2\) ở giữa, và số \(3\) bên phải) và \(n\) tấm đĩa tròn có kích thước khác nhau. Lúc đầu, ngăn xếp bên trái chứa tất cả đĩa theo thứ tự tăng dần về kích thước theo thứ tự từ trên xuống dưới đáy.

Mục tiêu là di chuyển tất cả tấm đĩa về ngăn xếp bên phải qua việc sử dụng ngăn xếp ở giữa. Ở mỗi lượt, bạn có thể chọn đĩa ở trên cùng của một ngăn xếp để chuyển nó tới một ngăn xếp khác. Ngoài ra, bạn không được phép đặt một chiếc đĩa lớn nằm trên một chiếc đĩa nhỏ hơn.

Nhiệm vụ của bạn là tìm ra lời giải sử dụng ít nước đi nhất.

Input

Gồm một dòng duy nhất chứa số nguyên \(n\) : số lượng đĩa.

Output

Dòng đầu tiên in số nguyên duy nhất \(k\) là số lượng nước đi tối thiểu tìm được.
Sau đó, in ra \(k\) dòng miêu tả các nước đi. Mỗi dòng có hai số nguyên \(a\) và \(b\): bạn di chuyển tấm đĩa từ ngăn xếp \(a\) sang ngăp xếp \(b\).

Constraints

\(1 \le n \le 16\)

Example

Sample input

Sample output

Note

Ví dụ cách chơi tối ưu với \(n = 5\) như sau:

Bình luận

def tower_of_hanoi(n, source, target, auxiliary, moves):
    if n == 1:
        moves.append((source, target))
    else:
        tower_of_hanoi(n-1, source, auxiliary, target, moves)
        moves.append((source, target))
        tower_of_hanoi(n-1, auxiliary, target, source, moves)

n = int(input())
moves = []
tower_of_hanoi(n, 1, 3, 2, moves)

print(len(moves))
for move in moves:
    print(move[0], move[1])

python 3 nha

5

penistone 4:24 p.m. 14 Tháng 11, 2023

Hint

K=2^n-1