We have N cards. A number a_i is written on the i-th card. Alice and Bob will play a…
- User
We have N cards. A number a_i is written on the i-th card. Alice and Bob will play a game using these cards. In this game, Alice and Bob alternately take one card. Alice goes first. The game ends when all the cards are taken by the two players, and the score of each player is the sum of the numbers written on the cards he/she has taken. When both players take the optimal strategy to maximize their scores, find Alice's score minus Bob's score.
Constraints
- N is an integer between 1 and 100 (inclusive).
- a_i \ (1 \leq i \leq N) is an integer between 1 and 100 (inclusive). Input
Input is given from Standard Input in the following format:
N a_1 a_2 a_3 ... a_N
Output
Print Alice's score minus Bob's score when both players take the optimal strategy to maximize their scores.
Examples
Input
2 3 1
Output
2
Input
3 2 7 4
Output
5
Input
4 20 18 2 18
Output
18
Assistant
We need to compute the difference in scores when both players play optimally to maximize their own scores, with Alice starting. This is a classic two-player zero-sum game where each player selects a card from the remaining ones; the sum of all numbers is fixed, so maximizing one's score is equivalent to maximizing the difference. However, the typical solution: sort descending, then Alice gets the largest, Bob gets the next, Alice gets next, etc. But is that optimal? Let's think: Since both players take one card alternately, with perfect play, the game is essentially: The optimal play for both players can be found by considering that the total sum of cards is S, and the difference D = (Alice_score - Bob_score). If both play optimally, the outcome can be computed via dynamic programming on the indices if the cards are in some order? But the players are free to choose any card from the set each turn. This is not a simple turn-based picking from ends of a line; it's arbitrary selection from a set. However, since the players can pick any card, the optimal strategy is greedy: sort the cards in descending order, and then in each turn, the player picks the largest remaining card. This is because the game is symmetric and the value of picking a card is exactly its number. In a zero-sum game where both players are rational, the optimal play is to take the largest available. Why? Suppose you have a set of numbers, and it's your turn. You want to maximize your final sum given the opponent will also pick optimally later. Since there's no positional effect (the order of picks doesn't affect future choices beyond removal of that card), the game reduces to both players picking the highest available card each turn. This can be argued by induction: if all cards are sorted a1 >= a2 >= ... >= aN. On your turn, picking the largest card gives you at least as much as picking any other, because any other card is less than or equal to the largest. And the opponent's subsequent picks will be from the reduced set. It might be not obvious because picking a smaller card could perhaps block the opponent from getting something? But since the opponent will also pick optimally, they will take the largest available on their turn anyway. If you don't take the largest, the opponent will take it on their next turn (if they get a turn before you get another chance). So you are better off taking the largest yourself. Formal proof: In a zero-sum game where both players have full information and moves consist of taking one item from a set, the optimal strategy is to take the largest item. This can be proven by considering that the game is a "take-away" game and the value is determined by the sum of the items you get. The game is equivalent to both players choosing a sequence of picks; the outcome if both play optimally is that the player who moves first gets the sum of items at odd positions after sorting descending (if the number of items is even, then Alice gets positions 1,3,5,...). This is a well-known result.
Thus, the answer is: sort numbers descending, then compute sum of numbers at odd indices (1-indexed) minus sum of numbers at even indices. That equals (sum of odd-indexed) - (sum of even-indexed). Alternatively, we could compute the sum of all numbers, and the difference is (sum of odd-indexed) - (sum of even-indexed). Also note that if we sort descending and assign alternately, the difference is also the sum of signs: + for Alice, - for Bob.
Given constraints N up to 100, we can simply sort and compute.
But wait: Check examples:
Example1: [3,1] sorted desc [3,1]: Alice takes 3, Bob takes 1 => difference 2. Output 2: matches.
Example2: [2,7,4] sorted desc [7,4,2]: Alice 7, Bob 4, Alice 2 => Alice sum 9, Bob 4, diff 5. Output 5: matches.
Example3: [20,18,2,18] sorted desc [20,18,18,2]: Alice 20, Bob 18, Alice 18, Bob 2 => Alice 38, Bob 20, diff 18. Output 18: matches.
Thus, answer matches.
Hence solution: read N, list a, sort reverse, compute diff = sum of a[0] + a[2] + ... minus sum of a[1] + a[3] + ... . Print diff.
Potential edge cases: N=1: Alice takes the only card, Bob 0, diff = that number. sorted desc [a1] => Alice gets a1, Bob 0 => diff a1. So works.
Thus answer.
But wait, is the problem more subtle? In some games, optimal strategy might be not simply greedy if the players' objectives are to maximize their own scores, not the difference, but since it's zero-sum, maximizing your score is equivalent to maximizing the difference. But is there any scenario where picking a non-largest could give you a larger total sum because it forces opponent to take a smaller later? For example, consider set [5,5,1]. Sorted desc [5,5,1]. Alice takes first 5, then Bob takes the other 5, Alice takes 1 => Alice total 6, Bob 5, diff 1. But what if Alice takes 1 first? Then Bob takes 5, Alice takes the other 5 => Alice total 6, Bob 5, diff 1. So same. But maybe there is case where taking a smaller gives a bigger advantage? Let's try [3,2,2]? Sorted desc [3,2,2]. Alice 3, Bob 2, Alice 2 => Alice 5, Bob 2 diff 3. If Alice takes 2 first, then Bob can take 3, Alice takes the other 2 => Alice 4, Bob 3 diff 1. So worse. So greedy is best.
But there might be a scenario with equal numbers? Doesn't matter.
Thus greedy is optimal.
However, is there a formal reasoning? Consider a set of numbers. The game can be seen as each player picks a number; the total sum is fixed, so the difference is 2*Alice_sum - total. To maximize Alice's sum, she wants to maximize her sum. At each move, she can take any remaining number. Since the opponent will also maximize his sum, which is equivalent to minimizing Alice's sum. The game value can be computed via DP on subsets but given constraints it's exponential. But the greedy solution holds because the numbers are all positive (since a_i >= 1). If numbers could be negative, the strategy might differ because you might want to force opponent to take negatives. But here all a_i are positive (1 to 100). So picking the largest is indeed optimal.
Thus answer straightforward.
But wait, some problems of this type have the twist that players alternately take a card, but they may not be able to see the whole set? No, full information.
So final solution: sort descending, then compute diff = sum_{i even index} - sum_{i odd index}? Let's define indexing 0-based: sorted[0] largest -> Alice; sorted[1] -> Bob; sorted[2] -> Alice; etc. So diff = (sorted[0] + sorted[2] + sorted[4] + ...) - (sorted[1] + sorted[3] + sorted[5] + ...). Equivalent to (sum of sorted) - 2*(sum of even positions starting from 1). So we can compute either.
Thus code:
def solve(): import sys input = sys.stdin.readline N = int(input().strip()) a = list(map(int, input().split())) a.sort(reverse=True) alice = sum(a[i] for i in range(0, N, 2)) bob = sum(a[i] for i in range(1, N, 2)) print(alice - bob)
But we can also compute difference directly:
diff = sum((-1)**i * a[i] for i in range(N))? That's not efficient; better to compute like above.
Alternatively, we can compute diff = sum(a[::2]) - sum(a[1::2]).
That works.
Complexity: O(N log N) due to sorting, which is fine.
Thus answer.
But let's ensure we interpret "Alice's score minus Bob's score". Yes.
Therefore, final solution. ```python
import sys
def solve() -> None: input = sys.stdin.readline N = int(input().strip()) a = list(map(int, input().split()))
# sort in descending order a.sort(reverse=True) # Alice gets indices 0,2,4,... ; Bob gets 1,3,5,... alice = sum(a[i] for i in range(0, N, 2)) bob = sum(a[i] for i in range(1, N, 2)) print(alice - bob)if name == "main": solve()