C++: Tìm người thắng cuộc thi toán

Bài toán: n bài, điểm ban đầu P[i], thời gian giải T[i]. Điểm bài i nộp lúc x: max(0, P[i] - c*x). Amal giải theo thứ tự 1..n, Bimal ngược n..1. Ai điểm cao hơn thắng.

Thuật toán

1. Amal: duyệt i=0..n-1, cộng dồn time, tính điểm.
2. Bimal: duyệt i=n-1..0, cộng dồn time, tính điểm.
3. So sánh tổng điểm.

Code C++

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

string solve(int c, vector<int> P, vector<int> T) {
    int n = P.size();
    long long timeA = 0, scoreA = 0, timeB = 0, scoreB = 0;

    for (int i = 0; i < n; i++) {
        timeA += T[i];
        scoreA += max(0, P[i] - c * timeA);
    }
    for (int i = n - 1; i >= 0; i--) {
        timeB += T[i];
        scoreB += max(0, P[i] - c * timeB);
    }

    if (scoreA > scoreB) return "Amal";
    if (scoreA < scoreB) return "Bimal";
    return "Tie";
}

int main() {
    int c = 2;
    vector<int> P = {50, 85, 250};
    vector<int> T = {10, 15, 25};
    cout << solve(c, P, T) << endl; // Amal
    return 0;
}

Kết quả

Amal