Editorial for mang: Bài tập mảng 1 chiều tổng hợp

Hiểu bài toán

Bài toán yêu cầu xử lý một mảng số nguyên và tính toán ba thông tin:

1. Tổng các số của dãy: Tổng aritmetich của tất cả các phần tử.
2. Số lượng số chẵn: Đếm số lượng phần tử chia hết cho 2.
3. Phần tử nguyên dương có chỉ số lớn nhất: Tìm giá trị dương ($>0$) xuất hiện cuối cùng trong mảng (vì chỉ số lớn nhất tương ứng với vị trí xét sau cùng).

Đầu vào gồm số lượng phần tử $n$ và $n$ số nguyên. Giới hạn $n \le 100$, các giá trị từ -1000 đến 1000.

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

Cách Một lần duyệt (One-pass)

#include <stdio.h>

int main() {
    int n;
    scanf("%d", &n);
    int tong = 0, cnt = 0, lastPositive = 0;

    for (int i = 0; i < n; i++) {
        int x;
        scanf("%d", &x);
        tong += x;
        if (x % 2 == 0) cnt++;
        if (x > 0) lastPositive = x;
    }

    printf("%d %d %d", tong, cnt, lastPositive);
    return 0;
}

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

Đây là cách tiếp cận hiệu quả nhất. Ta chỉ cần duyệt qua mảng một lần duy nhất:

1. Cộng dồn từng phần tử vào biến tong.
2. Kiểm tra nếu phần tử chia hết cho 2 thì tăng biến đếm cnt.
3. Nếu phần tử dương, gán giá trị đó vào biến lastPositive. Vì ta duyệt từ đầu đến cuối, giá trị gán sau cùng sẽ là giá trị dương có chỉ số (vị trí) lớn nhất.

Các biến số đều được khởi tạo mặc định là 0, nên nếu không có số dương nào, kết quả sẽ là 0 như yêu cầu.

Cách Hai lần duyệt (Separate Loops)

#include <stdio.h>

int main() {
    int n;
    scanf("%d", &n);
    int a[105];

    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }

    int tong = 0, cnt = 0;
    for (int i = 0; i < n; i++) {
        tong += a[i];
        if (a[i] % 2 == 0) cnt++;
    }

    int lastPositive = 0;
    for (int i = n - 1; i >= 0; i--) {
        if (a[i] > 0) {
            lastPositive = a[i];
            break;
        }
    }

    printf("%d %d %d", tong, cnt, lastPositive);
    return 0;
}

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

Cách tiếp cận này tách biệt logic tính toán:

1. Lần duyệt 1: Đọc dữ liệu và tính Tổng + Đếm số chẵn (hoặc đọc vào mảng trước rồi tính sau).
2. Lần duyệt 2: Duyệt ngược từ phần tử cuối cùng ($n-1$) về đầu để tìm phần tử dương đầu tiên gặp phải. Đây là phần tử dương có chỉ số lớn nhất.

Cách này tách rõ ràng các mục tiêu tính toán nhưng cần thêm bộ nhớ để lưu mảng và thực hiện nhiều thao tác duyệt hơn.

Cách Xử lý lỗi và ràng buộc (Robust Input)

#include <stdio.h>

int main() {
    int n;
    // Đọc n và kiểm tra ràng buộc (ví dụ n <= 100)
    do {
        scanf("%d", &n);
    } while (n > 100);

    int sum = 0, even_cnt = 0, last_pos = 0;

    for (int i = 0; i < n; i++) {
        int val;
        // Đọc giá trị và kiểm tra ràng buộc (ví dụ -1000 <= val <= 1000)
        do {
            scanf("%d", &val);
        } while (val < -1000 || val > 1000);

        sum += val;
        if (val % 2 == 0) even_cnt++;
        if (val > 0) last_pos = val;
    }

    printf("%d %d %d", sum, even_cnt, last_pos);
    return 0;
}

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

Đây là biến thể của giải pháp Một lần duyệt nhưng thêm các kiểm tra ràng buộc dữ liệu đầu vào (input validation) bằng vòng lặp do-while. Cách này đảm bảo dữ liệu nhập vào tuân thủ đúng giới hạn của đề bài (n <= 100, -1000 <= a_i <= 1000). Logic tính toán kết quả vẫn giữ nguyên.

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

Bài học kinh nghiệm

• Vấn đề 'chỉ số lớn nhất' tương đương với 'xuất hiện cuối cùng' trong danh sách. Do đó, duyệt tuần tự từ đầu và ghi đè biến dương là đủ, không cần dùng mảng.
• Biến lưu kết quả dương khởi tạo mặc định là 0, nên trường hợp 'không có số dương' được xử lý tự động mà không cần if-else rườm rà.

Lỗi thường gặp

• Lỗi Logic 'Chỉ số lớn nhất': Nếu dùng phương pháp duyệt ngược để tìm số dương đầu tiên, phải duyệt từ n-1 về 0. Nếu duyệt từ 0 lên và chỉ gán giá trị dương đầu tiên gặp (break ngay), ta sẽ得到 số dương có chỉ số nhỏ nhất, vi phạm yêu cầu đề bài.
• Trục trặc với số âm và số 0: Số 0 không phải là số nguyên dương. Câu lệnh điều kiện phải là x > 0, không được dùng x >= 0.