Editorial for ptit025: Cuộc thi!

Hiểu bài toán

Bài toán yêu cầu tìm ra sinh viên (hoặc các sinh viên) có tổng điểm 3 môn (Toán, Lí, C++) cao nhất. Đầu vào bao gồm số lượng sinh viên $n$, danh sách tên của họ, và danh sách điểm của 3 môn. Vì điểm số được cho riêng biệt cho từng môn, ta cần tổng hợp chúng lại cho từng sinh viên. Nếu có nhiều sinh viên cùng có tổng điểm cao nhất, tất cả đều được in ra theo thứ tự xuất hiện ban đầu.

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

Cách Quản lý dữ liệu theo từng môn (C)

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

struct Contest {
    char name[200];
    int math,physics,code;
};

typedef struct Contest ct;

void in(ct a[],int n){
    for (int i = 0; i < n; i++) {
        gets(a[i].name);
    }
    for (int i = 0; i < n; i++) {
        scanf("%d",&a[i].math);
    }
    for (int i = 0; i < n; i++) {
        scanf("%d",&a[i].physics);
    }
    for (int i = 0; i < n; i++) {
        scanf("%d",&a[i].code);
    }
}

void print(ct a) {
    printf("%s ",a.name);
    printf("%d %d %d",a.math,a.physics,a.code);
}

int main() {
    ct proptit[200];
    int n;
    scanf("%d",&n);
    getchar();
    in(proptit,n);
    int max = 0;
    for (int i = 0; i < n; i++) {
        int sum = proptit[i].math + proptit[i].physics + proptit[i].code;
        if (sum > max) max = sum;
    }
    for (int i = 0; i < n; i++) {
        if (max == proptit[i].math + proptit[i].physics + proptit[i].code) {
            print(proptit[i]);
            printf("\n");
        }
    }
    return 0;
}

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

Cách tiếp cận này sử dụng một struct để lưu trữ toàn bộ thông tin của một sinh viên (tên và 3 điểm). Chương trình đọc tất cả dữ liệu vào mảng các struct, sau đó tính tổng điểm cho từng sinh viên để tìm ra tổng điểm lớn nhất (max). Cuối cùng, duyệt lại mảng một lần nữa để in ra những sinh viên có tổng điểm bằng max.

Ưu điểm là logic rõ ràng, dữ liệu tập trung. Tuy nhiên, cần chú ý việc đọc tên (dùng gets hoặc fgets) và xử lý ký tự newline (\n) còn sót lại trước khi đọc số.

Cách Xử lý luồng dữ liệu (Stream Processing)

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

typedef struct{
    char name[100];
    int toan, li, cplus;
}Students;

int main() {
    int n, i;
    scanf("%d\n", &n);
    Students res[n];
    for (i = 0; i < n; i++) {
        fgets(res[i].name, 100, stdin);
        res[i].name[strlen(res[i].name) - 1] = '\0';
    }
    for (i = 0; i < n; i++) {
        scanf("%d", &res[i].toan);
    }
    for (i = 0; i < n; i++) {
        scanf("%d", &res[i].li);
    }
    for (i = 0; i < n; i++) {
        scanf("%d", &res[i].cplus);
    }
    int max = 0;
    for (i = 0; i < n; i++) {
        if (res[i].toan + res[i].li+res[i].cplus > max) {
            max=res[i].toan+res[i].li+res[i].cplus;
        }
    }
    for (i = 0; i < n; i++) {
        if (res[i].toan + res[i].li + res[i].cplus == max) {
            printf("%s %d %d %d\n", res[i].name, res[i].toan, res[i].li, res[i].cplus);
        }
    }
    return 0;
}

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

Giống approach 1, approach này cũng dùng struct. Tuy nhiên, nó tối ưu hóa việc nhập dữ liệu bằng cách sử dụng scanf("%d\n", &n) để tự động xử lý ký tự newline. Nó sử dụng fgets để đọc tên và loại bỏ ký tự newline cuối cùng bằng res[i].name[strlen(res[i].name) - 1] = '\0'. Logic tính điểm và in kết quả tương tự.

Cách Tích lũy điểm khi nhập (Single Pass)

#include<stdio.h>
int n;
char s[105][105];
int A[3][105];
int score[105];
int main() {
  scanf("%d", &n);
  scanf("\n");
  for (int i = 0; i < n; i++) gets(s[i]);
  int mxScore = 0;
  for (int k = 0; k < 3; k++){
    for (int i = 0; i < n; i++){
      scanf("%d", &A[k][i]);
      score[i] += A[k][i];
      if (k == 2){
        if (mxScore < score[i]) mxScore = score[i];
      }        
    }
  }
  for (int i = 0; i < n; i++){
    if (mxScore == score[i]){
      printf("%s %d %d %d\n", s[i], A[0][i], A[1][i], A[2][i]);
    }
  }
}

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

Approach này khác biệt ở chỗ nó không lưu struct. Nó sử dụng các mảng riêng biệt: mảng 2 chiều A[3][105] để lưu điểm số của 3 môn, mảng score để lưu tổng điểm tích lũy, và mảng s để lưu tên.

Trong vòng lặp đọc điểm, khi đọc đến môn thứ 3 (k == 2), nó cập nhật ngay tổng điểm lớn nhất (mxScore). Điều này giúp tiết kiệm một vòng lặp duyệt để tìm max sau khi nhập liệu xong.

Sau đó, nó chỉ cần duyệt một lần để in ra những sinh viên có tổng điểm bằng mxScore.

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

Bài học kinh nghiệm

• Đề bài cho phép nhiều người thắng cuộc, do đó cần tìm giá trị max trước, sau đó lọc lại danh sách để in.
• Cần kết hợp các điểm từ 3 mảng/luồng dữ liệu riêng biệt vào cùng một vị trí (cùng một sinh viên).
• Sử dụng fgets hoặc gets là bắt buộc để đọc tên đầy đủ (kể cả có khoảng trắng).

Lỗi thường gặp

• Lỗi nhập xuất (I/O): Xử lý ký tự newline (\n) sai lệch giữa scanf và gets/fgets.
• Giả sử rằng chỉ có duy nhất một người có tổng điểm cao nhất, trong khi đề bài cho phép nhiều người.
• Quên in các dấu cách giữa tên và các điểm số.