Hiểu bài toán

Bài toán yêu cầu tính giá trị của biểu thức lồng nhau $S_n = \sqrt{n + \sqrt{n-1 + \sqrt{... + \sqrt{2 + \sqrt{1}}}}}$. Với mỗi test case, ta cần in ra giá trị này làm tròn đến 5 chữ số thập phân. Do giới hạn $n$ lên tới $10^6$ và số lượng test $T$ lên tới $10^5$, ta cần một phương pháp tính toán hiệu quả.

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

Cách Mô phỏng đệ quy (Trực tiếp)

#include <stdio.h>
#include <math.h>

// Hàm tính toán đệ quy
double solve(int n) {
    if (n == 1) return sqrt(1);
    return sqrt(n + solve(n - 1));
}

int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        int n;
        scanf("%d", &n);
        printf("%.5lf\n", solve(n));
    }
    return 0;
}

• Time Complexity: O(n) mỗi test case, tổng thể O(T * n) ~ $10^{12}$ (Quá chậm)
• Space Complexity: O(n) (Do đệ quy)

Phương pháp này cố gắng tính trực tiếp giá trị của $S_n$ bằng cách gọi đệ quy từ $n$ về $1$. Với mỗi $n$, ta thực hiện một phép tính căn bậc hai và một phép cộng.

Tại sao lại chậm? Với $n = 10^6$ và $T = 10^5$, tổng số phép tính là $10^{11}$ đến $10^{12}$, quá lớn so với giới hạn thời gian (thường là $10^8$ phép tính/giây). Ngoài ra, đệ quy sâu $10^6$ có thể gây tràn bộ nhớ stack.

Cách Tính trước (Precomputation)

#include <stdio.h>
#include <math.h>

#define MAX_N 1000001
double S[MAX_N];

void precompute() {
    S[1] = sqrt(1);
    for (int i = 2; i < MAX_N; i++) {
        S[i] = sqrt(i + S[i-1]);
    }
}

int main() {
    precompute();
    int T;
    scanf("%d", &T);
    while (T--) {
        int n;
        scanf("%d", &n);
        printf("%.5lf\n", S[n]);
    }
    return 0;
}

• Time Complexity: O(MAXN) để tiền xử lý + O(T) để truy vấn. Với MAXN = $10^6$ và T = $10^5$, tổng thời gian ~ $1.1 \times 10^6$ thao tác, rất nhanh.
• Space Complexity: O(MAX_N) để lưu mảng (khoảng 8MB).

Đây là phương pháp tối ưu nhất. Ta nhận thấy giá trị $Sn$ chỉ phụ thuộc vào $n$ và không thay đổi theo test case. Do đó, ta có thể tính trước tất cả các giá trị $Si$ cho $i$ từ $1$ đến $10^6$ và lưu vào mảng.

Công thức tính: $Si = \sqrt{i + S{i-1}}$ với $S_1 = \sqrt{1}$. Với mỗi test case, ta chỉ cần tra cứu mảng để lấy kết quả in ra, tốn $O(1)$ thời gian.

Lưu ý indexing: Trong một số solution mẫu, a[0] = sqrt(1) và a[i] tính cho $i+1$. Tuy nhiên, cách minh họa ở trên (bắt đầu từ $S[1]$) rõ ràng hơn. Dù cách nào, ta cũng cần đảm bảo tra cứu đúng giá trị cho $n$.

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

Bài học kinh nghiệm

• Bài toán có tính chất quay lui (recurrence) $xn = f(x{n-1})$. Do đó có thể tính động.
• Vì $T$ lớn và $n$ nằm trong giới hạn cố định ($10^6$), việc tiền xử lý (precomputation) trước các kết quả là chìa khóa để giảm thời gian thực thi từ $O(T \times n)$ xuống $O(n + T)$.
• Độ chính xác của double là đủ để tính toán và làm tròn theo yêu cầu của đề bài.

Lỗi thường gặp

• Lỗi mảng tràn (Array Out of Bound): Khi khai báo mảng, cần đặt kích thước tối thiểu là $10^6 + 1$ (ví dụ 1000001) để tránh lỗi với $n=10^6$.
• Lỗi đệ quy quá sâu (Stack Overflow): Nếu cố gắng giải quyết bài toán này bằng đệ quy trực tiếp với $n=10^6$, chương trình sẽ bị crash.
• Không trừ hao bộ nhớ: Khi khai báo mảng double cỡ lớn (khoảng 8 byte/phần tử) cho $10^6$ phần tử, cần đảm bảo bộ nhớ khả dụng (khoảng 8MB).