Hiểu bài toán

Bài toán yêu cầu tìm số bước di chuyển tối thiểu để chuyển một chồng N đĩa từ cọc xuất phát sang cọc đích, với M cọc có sẵn (trong đó M-2 cọc làm trung gian).

Đây là bài toán tổng quát của bài toán Tháp Hà Nội kinh điển (M=3).

• Với M=3, lời giải là $2^N - 1$.
• Với M>3, ta có thể chia chồng đĩa thành 2 phần: $k$ đĩa trên cùng và $N-k$ đĩa dưới cùng.
  1. Chuyển $k$ đĩa lên một cọc trung gian (dùng $M$ cọc): tốn $dp[k][M]$ bước.
  2. Chuyển $N-k$ đĩa sang cọc đích (chỉ còn $M-1$ cọc để dùng làm trung gian): tốn $dp[N-k][M-1]$ bước.
  3. Chuyển $k$ đĩa từ cọc trung gian xuống cọc đích (dùng $M$ cọc): tốn $dp[k][M]$ bước. Tổng cộng: $2 \cdot dp[k][M] + dp[N-k][M-1]$. Ta cần tìm giá trị nhỏ nhất của biểu thức này với mọi $k$ từ $1$ đến $N-1$. Giá trị có thể rất lớn (lên đến $2^{64}$), cần loại số 128-bit.

Các cách tiếp cận

Cách Quy hoạch động (Dynamic Programming)

#include <bits/stdc++.h>
using namespace std;
using int128 = __int128; // Sử dụng 128-bit integer

int128 dp[65][65];

void solve() {
    // Khởi tạo cơ sở
    for (int m = 3; m <= 64; m++) {
        dp[0][m] = 0;
        dp[1][m] = 1;
    }
    // Tính toán
    for (int n = 2; n <= 64; n++) {
        for (int m = 3; m <= 64; m++) {
            if (m == 3) {
                // Công thức Tháp Hà Nội kinh điển
                dp[n][m] = ((int128)1 << n) - 1;
            } else {
                int128 best = -1; // Hoặc một giá trị rất lớn
                for (int k = 1; k < n; k++) {
                    int128 moves = 2 * dp[k][m] + dp[n - k][m - 1];
                    if (best == -1 || moves < best) {
                        best = moves;
                    }
                }
                dp[n][m] = best;
            }
        }
    }
}

int main() {
    solve();
    int T; cin >> T;
    while (T--) {
        int N, M; cin >> N >> M;
        // In số 128-bit
        if (dp[N][M] == 0) cout << "0\n";
        else {
            string s;
            int128 x = dp[N][M];
            while (x > 0) {
                s += (char)('0' + (x % 10));
                x /= 10;
            }
            reverse(s.begin(), s.end());
            cout << s << "\n";
        }
    }
    return 0;
}

• Time Complexity: O(T * N^2 * M) ~ 300 * 64^3 (nếu tính toán lại mỗi test) hoặc 64^3 (nếu precompute)
• Space Complexity: O(N * M) ~ 4096 phần tử

Sử dụng bảng quy hoạch động dp[n][m] để lưu số bước tối thiểu.

1. Base case: dp[1][m] = 1 (chỉ cần 1 bước để chuyển 1 đĩa).
2. Công thức đệ quy: dp[n][m] = min(2 * dp[k][m] + dp[n-k][m-1]) với k từ 1 đến n-1.
3. Với m=3, ta có thể dùng công thức toán học để tối ưu: dp[n][3] = 2^n - 1.
4. Do giá trị kết quả vượt quá giới hạn của unsigned long long (nên nhớ $2^{64}-1$ là lớn nhất cho 64-bit), ta phải dùng __int128 (tính năng mở rộng của GCC/Clang) hoặc BigNumber tự định nghĩa.

Cách Optimization (Tính chất đơn điệu)

// Giảm độ phức tạp từ O(N^2 * M) xuống O(N * M)
// Chỉ có thể áp dụng khi M >= N hoặc dùng heuristics
// Tuy nhiên, lời giải dưới đây là DP chuẩn đã tối ưu vòng lặp

void solve_optimized() {
    // ... (Initialization similar)
    for (int n = 2; n <= 64; n++) {
        for (int m = 3; m <= 64; m++) {
            if (m == 3) dp[n][m] = ((int128)1 << n) - 1;
            else {
                // Khi M đủ lớn, chia đôi cho tối ưu
                // Hoặc duyệt k từ 1 đến n-1
                // Có thể dùng Binary Search tìm k tối ưu nếu hàm có tính chất đơn điệu
                // (Thường k tối ưu nằm gần n/2 hoặc biên)
                int128 best = -1;
                for (int k = 1; k < n; k++) {
                    int128 moves = 2 * dp[k][m] + dp[n - k][m - 1];
                    if (best == -1 || moves < best) best = moves;
                }
                dp[n][m] = best;
            }
        }
    }
}

• Time Complexity: O(N^2 * M) (trong thực tế với N, M <= 64 là rất nhanh)
• Space Complexity: O(N * M)

Approach này về cơ bản là DP, nhưng có thể tối ưu thêm bằng cách nhận thấy rằng số đĩa chuyển xuống cọc đích (n-k) nên là 1 (chuyển trực tiếp) hoặc tối ưu theo tỷ lệ. Nếu M rất lớn so với N, ta có thể chia đôi N. Ví dụ, nếu M >= N, ta có thể chuyển trực tiếp hoặc chia đôi. Tuy nhiên, với ràng buộc N, M <= 64, DP thuần với vòng lặp k là đủ nhanh và dễ cài đặt nhất. Giải pháp này nhấn mạnh vào việc sử dụng int128 và cấu trúc DP.

Phân tích độ phức tạp

Bài học kinh nghiệm

• Công thức cơ bản: $f(n, m) = \min_{1 \le k < n} { 2 f(k, m) + f(n-k, m-1) }$.
• Trường hợp cơ sở: Khi chỉ còn 3 cọc ($m=3$), số bước là $2^n - 1$.
• Kiểu dữ liệu: Kết quả có thể lên tới $2^{64}-1$ hoặc lớn hơn một chút (vượt quá unsigned long long), cần dùng __int128 trong C++.

Lỗi thường gặp

• Sai kiểu dữ liệu: Dùng unsigned long long cho kết quả lớn hơn $2^{64}-1$ sẽ bị tràn số (overflow).
• Xử lý input/output: __int128 không được hỗ trợ bởi cin/cout mặc định, cần viết hàm chuyển đổi sang string.
• Lặp sai phạm vi k: Phải duyệt $k$ từ $1$ đến $N-1$, không bao gồm $0$ hoặc $N$ (vì nếu k=0, ta chỉ chuyển N đĩa với M-1 cọc, không có bước 1 và 3, nhưng về mặt logic DP vẫn đúng nếu ta coi dp[0]=0, nhưng thường k phải từ 1 để chia đôi).