P3878 [TJOI2010] Dividing Coins

There are $n$ coins, which may have different values. The value of the $i$-th coin is $v_i$. Now we need to split them into two parts such that the difference in the numbers of coins does not exceed $1$. What is the minimum possible difference between the total values of the two parts?

This problem contains multiple sets of testdata within a single test point. The first line contains a positive integer $T$, denoting the number of test cases in this test point. For each test case: Each test case consists of two lines. The first line contains an integer $n$, denoting the number of coins. The second line contains $n$ integers. The $i$-th integer denotes the value $v_i$ of the $i$-th coin.

For each test case, output one line with a single integer denoting the answer.

Constraints - For $30\%$ of the data, it is guaranteed that $1 \leq v_i \leq 1000$. - For $100\%$ of the testdata, it is guaranteed that $1 \leq T \leq 20$, $1 \leq n \leq 30$, $1 \leq v_i \leq 2^{30}$. Translated by ChatGPT 5