Tháp Hà Nội Cổ - LCOJ: Luyen Code Online

HNCO - Tháp Hà Nội Cổ

Điểm: 0,50 (OI)

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

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

Tác giả:

siro

Dạng bài

Ngôn ngữ cho phép

C, C#, C++, Go, Java, Pascal, Perl, PHP, 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

Output #1

Input #2

Output #2

Bình luận

Hãy đọc nội quy trước khi bình luận.

0

dinhvantung0611 đã bình luận lúc 10, Tháng 1, 2024, 8:11

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

-2

Solution:

#include <bits/stdc++.h>
using namespace std;

int main() {
 ios_base::sync_with_stdio(false);
 int n; cin >> n;
 if(n <= 50) cout << (1ULL << n) % 1000000007 - 1;
 else {
     int x = n/50, y = n%50;
     long long ans = 1;
     for(int i = 1; i <= x; i++) {
         ans = (ans * ((1ULL << 50) % 1000000007)) % 1000000007;
     }
     cout << (ans * ((1ULL << y) % 1000000007)) % 1000000007 - 1;
 }
}

-2

Solution:

#include <bits/stdc++.h>
using namespace std;

int main() {
 ios_base::sync_with_stdio(false);
 int n; cin >> n;
 if(n <= 50) cout << (1ULL << n) % 1000000007 - 1;
 else {
     int x = n/50, y = n%50;
     long long ans = 1;
     for(int i = 1; i <= x; i++) {
         ans = (ans * ((1ULL << 50) % 1000000007)) % 1000000007;
     }
     cout << (ans * ((1ULL << y) % 1000000007)) % 1000000007 - 1;
 }
}

0

thangtrung1101 đã bình luận lúc 15, Tháng 7, 2023, 3:54

admin cho em hỏi là Time Limit có bị sai ở đâu không ạ. Chứ em thử "cout << 1" vẫn bị TLE