HNCO - Tháp Hà Nội Cổ
Xem dạng PDF
Gửi bài giải
Điểm:
0,50 (OI)
Giới hạn thời gian:
0.5s
Giới hạn bộ nhớ:
256M
Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C#, C++, Go, Java, Pascal, Perl, PHP, PyPy, Python, Ruby, Rust, Scratch, Swift
Trong bài toán Tháp Hà Nội, có ~N~ đĩa theo thứ tự từ nhỏ đến lớn đang nằm ở cột ~A~ như hình bên dưới:
Cần chuyển ~N~ đĩa trên từ cột ~A~ sang cột ~C~ (lấy cột ~B~ làm cột trung gian) theo quy tắc:
- Mỗi lần chỉ chuyển một đĩa.
- Đĩa nhỏ phải nằm trên đĩa lớn tại bất kỳ thời điểm nào trong quá trình chuyển.
Câu hỏi như sau: Để chuyển ~N~ đĩa từ cột ~A~ sang cột ~C~ theo quy tắc trên, thì phải chuyển ít nhất bao nhiêu lần?
Input
Gồm ~1~ dòng duy nhất chứa số nguyên dương ~N (1 \le N \le 500)~.
Output
Gồm ~1~ dòng chứa duy nhất ~1~ số nguyên dương là kết quả của bài toán.
- Có thể đáp án cần in ra rất lớn, hãy in ra đáp án sau khi chia lấy dư cho ~10^9 + 7~
Sample
Input #1
2
Output #1
3
Input #2
5
Output #2
31
Bình luận
Bài toán tháp hà nội này số bước tối thiểu là 2^n - 1. Không dùng pow, nên viết hàm luỹ thừa nhị phân sẽ AC
admin cho em hỏi là Time Limit có bị sai ở đâu không ạ. Chứ em thử "cout << 1" vẫn bị TLE