Các điểm số có thể đạt được với n câu hỏi và trừ điểm trong C++

Giới thiệu

Cho n câu hỏi, mỗi câu đúng +x điểm, sai y điểm (y có thể âm). Học sinh có thể làm đúng, làm sai, hoặc bỏ qua. Tìm số lượng điểm số khác nhau có thể đạt được.

Mô hình hóa

Gọi:

• i = số câu đúng (0 ≤ i ≤ n)
• j = số câu bỏ qua (0 ≤ j ≤ n - i)
• n - i - j = số câu sai

Điểm số = i×x - (n-i-j)×y

Ví dụ

n = 20, x = 2, y = -1 (trừ 1 điểm cho sai)

Điểm = 2i - (20-i-j)×(-1) = 2i + 20 - i - j = i - j + 20

Với i,j ∈ [0,20], i+j ≤ 20 → i-j ∈ [-20, 20] → Điểm ∈ [0, 40] → 41 giá trị

Mã nguồn hoàn chỉnh

#include <bits/stdc++.h>
using namespace std;

int findPossibleMarksCount(int n, int x, int y) {
    set<int> marks;
    
    for (int i = 0; i <= n; i++) {        // Số câu đúng
        for (int j = 0; j <= n - i; j++) { // Số câu bỏ qua
            int wrong = n - i - j;
            int score = x * i + y * wrong; // y có thể âm
            marks.insert(score);
        }
    }
    
    return marks.size();
}

int main() {
    int n = 20, x = 2, y = -1;
    cout << "So diem khac nhau: " << findPossibleMarksCount(n, x, y) << endl;
    return 0;
}

Kết quả chạy chương trình

So diem khac nhau: 41

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

• Thời gian: O(n²) - hai vòng lặp lồng nhau
• Không gian: O(n²) - set lưu tối đa (n+1)(n+2)/2 giá trị

Tối ưu hóa toán học

Điểm số = i×x - (n-i-j)×y = i(x+y) + j×y - n×y

Với i ∈ [0,n], j ∈ [0,n-i], biểu thức này tạo ra một tập hợp các số nguyên. Có thể tìm min/max và bước nhảy để tính số lượng mà không cần set.

Mở rộng: In tất cả điểm số có thể

void printAllPossibleMarks(int n, int x, int y) {
    set<int> marks;
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= n - i; j++) {
            marks.insert(x * i + y * (n - i - j));
        }
    }
    cout << "Cac diem co the dat duoc: ";
    for (int m : marks) cout << m << " ";
    cout << endl;
}

Kết luận

Bài toán tổ hợp đơn giản nhưng minh họa tốt việc sử dụng set để loại bỏ trùng lặp. Với n lớn, cần giải pháp toán học O(1) hoặc O(n).