Hiểu bài toán

Bài toán yêu cầu tính giá trị của tổng S, được định nghĩa là tổng có dấu của các số nguyên từ 1 đến (3n+1). Quy tắc cộng trừ phụ thuộc vào tính chẵn lẻ của n:

• Nếu n là số chẵn: S = 1 - 2 + 3 - 4 + ... + (3n+1). Dấu '+' cho số lẻ, '-' cho số chẵn.
• Nếu n là số lẻ: S = 1 - 2 + 3 - ... - (3n+1). Dấu '+' cho số lẻ, '-' cho số chẵn. Lưu ý rằng số cuối cùng (3n+1) luôn có dấu âm/negate.

Đầu vào là số nguyên dương n (n < 200,000). Đầu ra là giá trị S.

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

Cách Vòng lặp (Simulation)

#include <stdio.h>
int main(){
    int n;
    scanf("%d", &n);
    int tong = 0;
    for(int i=1;i<=(3*n+1);i++){
        if(i%2==0) tong-=i; // Nếu chẵn thì trừ
        else tong+=i;       // Nếu lẻ thì cộng
    }
    printf("%d", tong);
    return 0;
}

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

Cách tiếp cận này mô phỏng chính xác định nghĩa của bài toán. Chương trình duyệt qua từng số nguyên từ 1 đến (3n+1). Nếu số đó là số lẻ, nó được cộng vào tổng. Nếu là số chẵn, nó được trừ đi. Với n tối đa là 200,000, số lượng các số cần duyệt là khoảng 600,000, hoàn toàn nằm trong giới hạn thời gian cho phép của hầu hết các hệ thống chấm bài.

Cách Công thức toán học (Optimized)

#include <stdio.h>

int main() {
    int n;
    scanf("%d", &n);

    long long sum_le, sum_chan, S;
    int m = 3 * n + 1;

    // Tính tổng các số lẻ từ 1 đến m
    // Số lượng số lẻ: (m + 1) / 2
    // Tổng số lẻ: (số lượng)^2
    long long count_le = (m + 1) / 2;
    sum_le = count_le * count_le;

    // Tính tổng các số chẵn từ 1 đến m
    // Số lượng số chẵn: m / 2
    // Tổng số chẵn: số lượng * (số lượng + 1)
    long long count_chan = m / 2;
    sum_chan = count_chan * (count_chan + 1);

    // Công thức chung: S = Tổng số lẻ - Tổng số chẵn
    // Ngay cả khi n lẻ, công thức này vẫn đúng vì (3n+1) là số chẵn (vì 3n lẻ, +1 thành chẵn).
    // Nếu n lẻ, (3n+1) nằm trong nhóm số chẵn nên bị trừ.
    // Nếu n chẵn, (3n+1) nằm trong nhóm số lẻ nên được cộng.
    S = sum_le - sum_chan;

    printf("%lld", S);

    return 0;
}

• Time Complexity: O(1)
• Space Complexity: O(1)

Đây là cách tiếp cận tối ưu, chạy ngay lập tức bất kể n lớn thế nào (trong giới hạn kiểu dữ liệu). Ta có thể phân tích tổng S thành tổng các số lẻ và tổng các số chẵn:

• Tổng các số lẻ từ 1 đến m là: 1 + 3 + ... + m = [(số lượng số lẻ)]^2 = [((m+1)/2)]^2.
• Tổng các số chẵn từ 1 đến m là: 2 + 4 + ... + m = 2 * (1 + 2 + ... + m/2) = 2 * [((m/2)*(m/2+1))/2] = (m/2) * (m/2 + 1). Giá trị S cuối cùng bằng Tổng số lẻ trừ đi Tổng số chẵn. Điểm mấu chốt: Dù n chẵn hay lẻ, (3n+1) luôn là số chẵn. Do đó, số cuối cùng luôn thuộc nhóm số chẵn và luôn bị trừ đi. Do đó, công thức S = (Tổng số lẻ) - (Tổng số chẵn) là công thức tổng quát và chính xác cho mọi n.

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

Bài học kinh nghiệm

• Số cuối cùng của dãy là (3n+1). Vì 3n luôn chia hết cho 3 và cùng dấu với n, nhưng khi xét chẵn lẻ: nếu n chẵn, 3n chẵn, 3n+1 lẻ. Nếu n lẻ, 3n lẻ, 3n+1 chẵn. Tuy nhiên, phép tính S là tổng dãy 1 đến 3n+1 với quy tắc dấu chẵm-lẻ chuẩn. Dựa vào định nghĩa bài toán: 'nếu n chẵn: ...+(3n+1)' và 'nếu n lẻ: ...-(3n+1)'.
• Có thể rút gọn phép tính bằng cách tách riêng tổng các số lẻ và tổng các số chẵn. Tổng các số lẻ từ 1 đến N là bình phương của số lượng số lẻ. Tổng các số chẵn từ 1 đến N là số lượng số chẵn nhân với số lượng số chẵn cộng 1.

Lỗi thường gặp

• Sử dụng kiểu dữ liệu int cho biến tổng (sum) có thể gây tràn số (overflow) nếu n đủ lớn. Nên sử dụng long long cho biến tổng.
• Việc hiểu sai quy tắc dấu cho trường hợp n lẻ. Nếu n lẻ, công thức là trừ số cuối, nhưng các số ở vị trí chẵn/lẻ khác vẫn giữ nguyên quy tắc 1-2+3-... (tức là số lẻ cộng, số chẵn trừ).