P10335 [UESTCPC 2024] Number Picking Game

There is a sequence of length $n$. The weight of the $i$-th number is $a_i$. Two players, A and B, are playing a game. They will take turns performing operations on the sequence. Each player has two choices each turn: - Delete any two numbers $a_i, a_j$ $(i \neq j)$ from the sequence, and add a new number with weight $a_i + a_j$ into the sequence. When there is only one number in the sequence, this operation cannot be performed. - Take away one number from the sequence, add up the weights of all remaining numbers and give the total to the opponent, then end the game. If A ends up with a larger total weight, then A wins; otherwise, B wins. A moves first. Determine whether A has a winning strategy. **It is guaranteed that the sum of $a_i$ is odd.**

This problem contains multiple test cases. The first line contains an integer $T$ $(1\leq T\leq 10^5)$, denoting the number of test cases. For each test case, the input format is as follows. The first line contains an integer $n$ $(1\leq n\leq 5 \times 10^5)$, denoting the initial length of the sequence. The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ $(1\leq a_i\leq 10^9)$, denoting the initial sequence. It is guaranteed that $\sum n\leq 10^6$ and $\sum a_i$ is odd.

For each test case, if A has a winning strategy, output `YES`; otherwise output `NO`.

The explanation for Sample 1 is as follows: - If A chooses the number with weight $3$, then the weight B can get is $6+4=10$. - If A chooses the number with weight $4$, then the weight B can get is $3+6=9$. - If A chooses the number with weight $6$, then the weight B can get is $3+4=7$. - If A chooses to merge weights $3,6$, the sequence becomes $9,4$. If B chooses the number with weight $9$, then the weight A can get is $4$. - If A chooses to merge weights $3,4$, the sequence becomes $7,6$. If B chooses the number with weight $7$, then the weight A can get is $6$. - If A chooses to merge weights $4,6$, the sequence becomes $10,3$. If B chooses the number with weight $10$, then the weight A can get is $3$. In all cases, B can obtain a higher total weight by playing optimally, so A cannot win. The explanation for Sample 2 is as follows: If A chooses the number with weight $2$, then the weight B can get is $1$. Therefore, A has a winning strategy. Translated by ChatGPT 5