Editorial for fcdem: Đếm số âm, dương trong mảng

Hiểu bài toán

Bài toán yêu cầu đếm số lượng số nguyên dương và số nguyên âm trong một dãy gồm N số nguyên. Dãy có thể chứa các số rất lớn (đến $10^{30}$), do đó cần chú ý đến kiểu dữ liệu khi lưu trữ và xử lý. Đầu vào bao gồm số lượng phần tử N và danh sách N số nguyên. Đầu ra là hai số: số lượng số âm và số lượng số dương (theo thứ tự này, dựa trên sample output).

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

Cách Duyệt và Đếm bằng Kiểu số

#include <stdio.h>

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

    long long sum = 0; // Bien dem so am
    long long res = 0; // Bien dem so duong
    for (int i = 0; i < n; ++i) {
        long long p;
        scanf("%lld", &p);
        if (p < 0) sum++;
        else if (p > 0) res++;
    }
    printf("%lld %lld", sum, res);
    return 0;
}

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

Đây là cách tiếp cận trực quan nhất. Ta đọc từng số nguyên bằng kiểu long long (vì số có thể lên tới $10^{30}$, vượt quá giới hạn của int nhưng long long chỉ chứa được tối đa khoảng $10^{18}$). Tuy nhiên, trong các kỳ thi thực tế với ngôn ngữ C/C++, long long thường là kiểu số nguyên lớn nhất được hỗ trợ chuẩn. Nếu số đầu vào thực sự lớn hơn $10^{18}$, cách này sẽ bị sai. Tuy nhiên, dựa trên các giải pháp nộp (Solution 1, 3) sử dụng long long, ta có thể giả định dữ liệu đầu vào nằm trong phạm vi này hoặc hệ thống test không bao gồm số quá lớn. Ta chỉ cần so sánh giá trị đọc được với 0 và tăng biến đếm tương ứng.

Cách Xử lý Chuỗi Ký tự (String Processing)

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

int main(){
    int n;
    scanf("%d",&n);
    int a = 0, b = 0; // a: so am, b: so duong
    for(int i = 1; i <= n; i++){
        char x[35]; // Kich thuoc du de chua so 10^30 va ki tu am
        scanf("%s", x);
        if(x[0] == '0') continue; // Xet truong hop so 0
        else if(x[0] == '-') a++; // Neu bat dau bang dau am thi la so am
        else b++; // Nguoc lai la so duong
    }
    printf("%d %d", a, b);
    return 0;
}

• Time Complexity: O(N * L)
• Space Complexity: O(L)

Giải pháp này xử lý số nguyên như một chuỗi ký tự để vượt qua giới hạn của kiểu dữ liệu số. Ta chỉ cần kiểm tra ký tự đầu tiên của chuỗi:

• Nếu là '-', số đó là số âm.
• Nếu là '0', số đó là số 0 (không tính là dương hay âm).
• Các trường hợp khác là số dương. Phương pháp này an toàn tuyệt đối cho mọi giới hạn giá trị tuyệt đối của số, miễn là số đó có thể được lưu dưới dạng chuỗi trong bộ nhớ.

Cách Tối ưu hóa Duyệt

#include <stdio.h>

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

    long long count_pos = 0, count_neg = 0;
    long long num;

    for (int i = 0; i < n; ++i) {
        scanf("%lld", &num);
        // Ternary operator for concise code
        (num > 0) ? count_pos++ : ((num < 0) ? count_neg++ : 0);
    }

    printf("%lld %lld", count_neg, count_pos);
    return 0;
}

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

Đây là biến thể của Approach 1, sử dụng cú pháp ngắn gọn hơn (nếu-else lồng hoặc toán tử 3 ngôi) để kiểm tra điều kiện. Về bản chất logic vẫn giống nhau: đọc số, so sánh với 0, và tăng biến đếm. Độ phức tạp không đổi.

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

Bài học kinh nghiệm

• Phân tích yêu cầu đầu ra: Sample output '3 1' cho input '-5 -3 -1 1' cho thấy thứ tự in ra là (Số âm, Số dương).
• Giới hạn giá trị: Với $|a_i| \le 10^{30}$, kiểu int hay long long ở C/C++ thông thường không đủ. Tuy nhiên, các giải pháp chấp nhận thường giả định dữ liệu nằm trong giới hạn long long hoặc sử dụng kỹ thuật chuỗi.
• Số 0: Cần xử lý rõ ràng số 0 (không phải dương cũng không phải âm). Solution 2 đã xử lý trường hợp '0'.

Lỗi thường gặp

• Lỗi kiểu dữ liệu (Integer Overflow): Sử dụng int hoặc long long cho các số trị giá $10^{30}$ sẽ gây tràn số.
• Thứ tự in sai: In ra 'số dương số âm' thay vì 'số âm số dương' như yêu cầu.
• Quên xử lý số 0: Coi số 0 là số dương hoặc số âm.