Jellyfish and Game (Codeforces 1874A)
Tags: Greedy, games

Jellyfish has $$$n$$$ green apples with values $$$a_1, a_2, \dots, a_n$$$ and Gellyfish has $$$m$$$ green apples with values $$$b_1,b_2,\ldots,b_m$$$.They will play a game with $$$k$$$ rounds. For $$$i=1,2,\ldots,k$$$ in this order, they will perform the following actions:   If $$$i$$$ is odd, Jellyfish can choose to swap one of her apples with one of Gellyfish's apples or do nothing.  If $$$i$$$ is even, Gellyfish can choose to swap one of his apples with one of Jellyfish's apples or do nothing. Both players want to maximize the sum of the values of their apples.Since you are one of the smartest people in the world, Jellyfish wants you to tell her the final sum of the value of her apples after all $$$k$$$ rounds of the game. Assume that both Jellyfish and Gellyfish play optimally to maximize the sum of values of their apples.

Input: Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \leq t \leq 2000$$$). The description of the test cases follows.The first line of each test case contains three integers, $$$n$$$, $$$m$$$ and $$$k$$$ ($$$1 \leq n, m \leq 50$$$, $$$1 \leq k \leq 10^9$$$) — the number of green apples Jellyfish has, the number of green apples Gellyfish has and the number of rounds of the game respectively.The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — the values of Jellyfish's green apples.The third line of each test case contains $$$m$$$ integers $$$b_1, b_2, \dots, b_m$$$ ($$$1 \leq b_i \leq 10^9$$$) — the values of Gellyfish's green apples.Do note that the sum of $$$n$$$ and $$$m$$$ over all test cases are both not bounded.

Output: For each test case, output a single integer — the final sum of the values of Jellyfish's apples.

Note: In the first test case, Jellyfish will swap the apple of value $$$1$$$ and $$$4$$$.In the second test case, both players will swap the two apples $$$10,000$$$ times.In the fourth test case, Jellyfish will do nothing.

Sample Inputs:
4
2 2 1
1 2
3 4
1 1 10000
1
2
4 5 11037
1 1 4 5
1 9 1 9 8
1 1 1
2
1

Sample Outputs:
6
1
19
2

Solution (Python):
def jellyfishandGame(n, m, k, ns, ms):
    loop = 0
    if k % 2 == 0:
        loop = 2
    else:
        loop = 1
    for i in range(1, loop + 1):
        if i % 2 == 1:
            minVal = min(ns)
            maxVal = max(ms)
            minIndex = ns.index(minVal)
            maxIndex = ms.index(maxVal)
            if minVal < maxVal:
                ns[minIndex] = maxVal
                ms[maxIndex] = minVal
        else:
            minVal = min(ms)
            maxVal = max(ns)
            minIndex = ms.index(minVal)
            maxIndex = ns.index(maxVal)
            if minVal < maxVal:
                ms[minIndex] = maxVal
                ns[maxIndex] = minVal
    return sum(ns)

def playGame():
    t = int(input())
    results = ''
    for i in range(t):
        (n, m, k) = map(int, input().split())
        ns = list(map(int, input().split()))[:n]
        ms = list(map(int, input().split()))[:m]
        if i == t - 1:
            results = results + str(jellyfishandGame(n, m, k, ns, ms))
        else:
            results = results + str(jellyfishandGame(n, m, k, ns, ms)) + '\n'
    print(results)
playGame()

Solution (Python):
def solve(n, m, k, a, b):
    mxa = max(a)
    mxb = max(b)
    mx = max(mxa, mxb)
    mna = min(a)
    mnb = min(b)
    mn = min(mna, mnb)
    total_sum = sum(a)
    if mxb > mna:
        total_sum += mxb
        total_sum -= mna
    if k % 2 == 1:
        return total_sum
    else:
        return total_sum - mx + mn
t = int(input())
anses = []
for _ in range(t):
    (n, m, k) = list(map(int, input().split()))
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    anses.append(solve(n, m, k, a, b))
for ans in anses:
    print(ans)

Solution (Python):
def solve(n, m, k, a, b):
    mxa = max(a)
    mxb = max(b)
    mx = max(mxa, mxb)
    mna = min(a)
    mnb = min(b)
    mn = min(mna, mnb)
    total_sum = sum(a)
    if mxb > mna:
        total_sum += mxb
        total_sum -= mna
    if k % 2 == 1:
        return total_sum
    else:
        return total_sum - mx + mn
t = int(input())
anses = []
for _ in range(t):
    (n, m, k) = list(map(int, input().split()))
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    anses.append(solve(n, m, k, a, b))
for ans in anses:
    print(ans)