หาคะแนนสอบที่เป็นไปได้ทั้งหมดกับการให้คะแนนลบใน C++

บทนำ

โจทย์: มี n ข้อ ข้อถูก +x คะแนน ข้อผิด -y คะแนน ข้อไม่ตอบ 0 คะแนน หาจำนวนคะแนนรวมที่เป็นไปได้ทั้งหมด

ขั้นตอนการแก้ปัญหา

1. วนลูป i = 0 ถึง n (จำนวนข้อถูก)
2. วนลูป j = 0 ถึง n (จำนวนข้อไม่ตอบ)
3. ข้อผิด = n - i - j
4. คะแนน = x*i - y*(n - i - j)
5. เก็บคะแนนใน set (กันซ้ำ)
6. คืนขนาด set

ตัวอย่างโค้ด

#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++) {
        for (int j = 0; j <= n; j++) {
            // i = correct, j = not_answered
            marks.insert((x * i) - ((n - i - j) * y));
        }
    }
    return marks.size();
}

int main() {
    int n = 20, x = 2, y = -1;
    cout << findPossibleMarksCount(n, x, y) << endl;
}

ผลลัพธ์

41

คำอธิบาย

n=20, x=2, y=-1 (ข้อผิดหัก 1 คะแนน) คะแนนขั้นต่ำ: ทำผิดทั้งหมด = -20 คะแนนสูงสุด: ทำถูกทั้งหมด = 40 ช่วง -20 ถึง 40 มี 41 ค่า ทั้งหมดเป็นไปได้

สรุป

ใช้ set กรองค่าซ้ำได้ง่าย ความซับซ้อน O(n²) เหมาะกับ n ≤ ~1000 สำหรับ n ใหญ่ต้องใช้คณิตศาสตร์หาช่วงค่าที่เป็นไปได้โดยตรง