Hiểu bài toán

Bài toán yêu cầu tính tổng các số nghịch đảo của dãy số lẻ: Sn = 1 + 1/3 + 1/5 + ... + 1/(2n-1). Với T test case và mỗi test cho một số nguyên dương n (1 ≤ n ≤ 10^6), cần in ra Sn được làm tròn đến 5 chữ số thập phân. Do T có thể lên tới 10^5, chúng ta cần một phương pháp hiệu quả để xử lý nhiều truy vấn nhanh chóng.

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

Cách Tính toán trực tiếp (Mỗi test)

#include <stdio.h>

int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        int n;
        scanf("%d", &n);
        double sum = 0.0;
        for (int i = 1; i <= n; i++) {
            sum += 1.0 / (2 * i - 1);
        }
        printf("%.5lf\n", sum);
    }
    return 0;
}

• Time Complexity: O(T * n)
• Space Complexity: O(1)

Phương pháp này xử lý từng test case một cách độc lập. Với mỗi n, nó chạy một vòng lặp từ 1 đến n để tính tổng các phân số.

• Ưu điểm: Đơn giản, không cần bộ nhớ phụ.
• Nhược điểm: Rất chậm. Với T=10^5 và n=10^6, số phép tính là 10^11, chắc chắn gây TLE (Time Limit Exceeded).

Cách Tiền xử lý mảng (Precomputation)

#include <stdio.h>
#include <stdlib.h>

#define MAX_N 1000000

int main() {
    // Phân bổ bộ nhớ cho mảng kết quả
    double *S = (double *)malloc((MAX_N + 1) * sizeof(double));
    if (S == NULL) return 1;

    // Tính toán trước
    S[0] = 0.0;
    for (int i = 1; i <= MAX_N; i++) {
        S[i] = S[i - 1] + 1.0 / (2 * i - 1);
    }

    // Xử lý truy vấn
    int T;
    scanf("%d", &T);
    while (T--) {
        int n;
        scanf("%d", &n);
        printf("%.5lf\n", S[n]);
    }

    free(S);
    return 0;
}

• Time Complexity: O(MAX_N + T) ~ O(10^6)
• Space Complexity: O(MAX_N) ~ O(10^6)

Đây là cách tiếp cận tối ưu được sử dụng trong các bài nộp accepted.

1. Xác định n lớn nhất có thể (10^6).
2. Tạo một mảng S lưu giá trị S_n cho mọi n từ 0 đến 10^6.
3. Sử dụng quy hoạch động: S[i] = S[i-1] + 1/(2i-1). Tính toán các giá trị này trước một lần.
4. Khi nhận truy vấn, chỉ cần tra cứu mảng và in kết quả ngay lập tức.

• Ưu điểm: Rất nhanh cho nhiều test case, chỉ tốn O(1) thời gian cho mỗi test sau khi tiền xử lý.
• Nhược điểm: Tốn bộ nhớ để lưu mảng (khoảng 8MB cho 1 triệu số thực double).

Cách Sử dụng biến toàn cục (Global Array)

#include <stdio.h>

#define MAX_N 1000000

// Khai báo mảng toàn cục để tự động khởi tạo bằng 0
double sum[MAX_N + 1];

int main() {
    // Tiền xử lý ngay trong main
    // Lưu ý: sum[0] mặc định là 0.0
    for (int i = 1; i <= MAX_N; ++i) {
        sum[i] = sum[i - 1] + 1.0 / (2 * i - 1);
    }

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

• Time Complexity: O(MAX_N + T)
• Space Complexity: O(MAX_N)

Đây là biến thể của phương pháp tiền xử lý. Thay vì dùng malloc, ta khai báo mảng kích thước cố định ở phạm vi toàn cục.

• Ưu điểm: Tránh lỗi cấp phát bộ nhớ động, mã nguồn ngắn gọn hơn.
• Nhược điểm: Kích thước mảng cố định, phụ thuộc vào quy định của bộ biên dịch (nhưng 10^6 là an toàn).

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

Bài học kinh nghiệm

• Kỹ thuật tiền xử lý (Precomputation) là chìa khóa để giải quyết các bài toán có nhiều truy vấn với giới hạn dữ liệu cố định.
• Sử dụng quy hoạch động (Dynamic Programming) để tính toán các tổng tích lũy: S[i] = S[i-1] + phần tử mới.

Lỗi thường gặp

• Sử dụng số nguyên để tính phép chia (ví dụ: 1/3 sẽ ra 0). Phải ép kiểu hoặc thêm '.0' (1.0/3) để sử dụng số thực.
• Quên trừu tượng hóa giới hạn (hardcode) kích thước mảng quá nhỏ hoặc quá lớn.
• Xử lý sai thứ tự in kết quả nếu không lưu trữ trước (ví dụ: in ra kết quả tính được sau khi vòng lặp tính toán bị ảnh hưởng bởi input trước đó).