Problem D: Hansel and Gretel

Hansel and Gretel are wandering in the woods when an evil witch gives them a bucket of chocolate. In the bucket there are a variable number of chocolate bars, from 0 to 1000. The bars can weigh any amount, from 1 to 1000 grams, but will always be an exact integer value. That is bars can weigh 1 gram, 2 grams, 3 grams, and so on, and will never have a fractional weight such as 1.5 grams or 3.75 grams. The witch is evil because it is very hard for Hansel and Gretel to divide the chocolate fairly, causing them to get into very bad arguments. Your task is to help prevent Hansel and Gretel from fighting by dividing the chocolate for them.

Input

The first line of input will contain a single integer, b, indicating the number of buckers of chocolate you will have to divide. After this, there are b sets of data, one for each bucker. Each set of data begins with a single integer, n, indicating the number of chocolate bars in the bucket. Then, the next n lines will each contain a single integer indicating the weight of a bar of chocolate.

Output

You are tow output two integers, on the same line, with a single space between them. The first integer is the amount of chocolate that Gretel gets and the second integer is the amount of chocolate that Hansel gets. You must ensure that the difference between Hansel’s and Gretel’s amounts in minimal for each bucker. If the bucket can not be divided into two even sized piles, Gretel will get the larger pile.

Example Input                                               Example Output

2                                                                                              7  7
4                                                                                              2  1
2
3
4
5
3
1
1
1

==================================================================================

Well~~~ Actually, this problem is quite easy.

First read in the a single integer for the counter of total dividing times.

Then get the counter for the number of chocolate bars in the bucket. It is used for identifying the end of each dividing.

Then, it comes the most trick part of this problem. Since from the question, we know that we just have integer and we can not cut the bar into two pieces. So, what I thought was about comparing the difference of each possible combination of the half number of the bars. If there is a combination which the difference is zero, then the bucket of chocolate can be divided equally. If not, we get the combination with smallest difference and do as the question said, let Gretel get the larger pile.

Now, the problem is how can we do the "comparing the difference of each possible combination of the half number of the bars". One method I had at that time was doing by two arrays. Put first half into an array(array_1) and the rest into another array(array_2). Removing the first element in array and adding each element in array_2. Comparing the difference each time and store the smallest difference and the combination. And restore the removed element and remove the next one.

It looks like almost solved, but we still have a tiny problem. If the number of chocolate is odd, how to set the two arrays. Well, it is easy, just add one element with zero value into the end array_2, and do the same thing as even number of chocolate.

At this point, we can say the problem is solved. What left is just some coding part.

 

Some pics took during this event:

At daytime, the MacBook is onwed by her really onwer.

But when the dark comes, MacBook becomes my biotch.

Waiting for the programming competition.  

The Banquet