In this card game challegne, two participants, C and S, each hold $n$ cards with integer values. Over $n$ rounds, both players draw one card per round. The scoring rules are: 3 points for the higher card, 1 point for the lower card, and 2 points each if the values are equal. The goal is to detemrine the maximum and minimum total points S can achieve against C.

Strategy

This problem can be effectively solved using a greedy strategy similar to the classic "Tian Ji Horse Racing" algorithm. By sorting both sets of cards, we can decide how to pair cards to either maximize or minimize S's score.

To find the maximum points, S should prioritize winning rounds by comparing their best remaining card against C's best. If S cannot win, they should sacrifice they weakest card against C's strongest to minimize the loss.

Implementation

The following C++ implementation calculates the maximum score using the greedy approach. The minimum score is derived by calculating the maximum points C can gain against S and subtracting that from the total possible points ($4n$).

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int calculate_score(const vector<int>& opp, const vector<int>& self, int count) {
    int score = 0;
    int opp_start = 0, opp_end = count - 1;
    int self_start = 0, self_end = count - 1;

    while (self_start <= self_end) {
        if (self[self_end] > opp[opp_end]) {
            score += 3;
            self_end--;
            opp_end--;
        } else if (self[self_start] > opp[opp_start]) {
            score += 3;
            self_start++;
            opp_start++;
        } else {
            if (self[self_start] == opp[opp_end]) {
                score += 2;
            } else {
                score += 1;
            }
            self_start++;
            opp_end--;
        }
    }
    return score;
}

int main() {
    int n;
    while (cin >> n && n != 0) {
        vector<int> cards_c(n), cards_s(n);
        for (int i = 0; i < n; ++i) cin >> cards_c[i];
        for (int i = 0; i < n; ++i) cin >> cards_s[i];

        sort(cards_c.begin(), cards_c.end());
        sort(cards_s.begin(), cards_s.end());

        int max_pts = calculate_score(cards_c, cards_s, n);
        int min_pts = 4 * n - calculate_score(cards_s, cards_c, n);

        cout << max_pts << " " << min_pts << endl;
    }
    return 0;
}