1.

/*

* FWP, Ausgew¦hlte Probleme aus dem ACM Programming Contest, SS10

* Problem: 10032 tug of war

*

* @author Martin Lambeck

* @version 1.0, 31.10.2010

*

* Method : dp

* Status : Accepted

* Runtime: 1.544

*

*/

#include <stdio.h>

#include <memory.h>

#define WEIGHT_RANGE 90001

#define OFFSET 45000

bool first = true;

typedef unsigned long long uint64;

//if a[X] has the bit Y (starting at 0) set,

//then there is a configuration where exactly Y people are in group 1, and the sum of their weights is X.

//multiple bits can be set

uint64 *a = new uint64[WEIGHT_RANGE];

uint64 *b = new uint64[WEIGHT_RANGE];

int weight[101]; //weight of the people

void testcase()

{

int pers, sum=0;//number of person, sum of weights

scanf("%d", &pers);

for (int i = 0; i < pers; i++)

scanf("%d", weight+i);

for (int i = 0; i < pers; i++)

sum += weight[i];

memset(a, (uint64) 0, WEIGHT_RANGE * sizeof(uint64)); //clear

a[OFFSET + weight[0]] = 2; //bit 1 (starting at 0)

a[OFFSET - weight[0]] = 1; //bit 0

uint64 *prev = b, *cur = a, *tmp;

for (int i = 1; i < pers; i++)

{

tmp = cur; //use only two arrays, but alternate them on each run

cur = prev; //cur is to be filled (clear before)

prev = tmp; //prev is the array of the previous person

int w = weight[i];

memset(cur, (uint64) 0, WEIGHT_RANGE * sizeof(uint64));

for (int j = 0; j < WEIGHT_RANGE; j++)

{

if (prev[j] > 0)

{

cur[j+w] |= prev[j] << 1; //add person i to group 1

cur[j-w] |= prev[j]; //add person i to group 2

}

}

}

int diff = -1; //difference of total weight between the two teams

uint64 p1 = pers/2; //half of the people must be in group 1

uint64 p2 = (pers+1)/2; //if the number of persons is odd...

uint64 pattern = ((uint64)1 << p1) | ((uint64)1 << p2); //bitmask

for (int i = 0; i <= OFFSET && diff < 0; i++)

if (((cur[OFFSET+i] | cur[OFFSET-i]) & pattern) > 0)

diff = i; //optimal solution

printf("%s%d %d\n", first ? "" : "\n", (sum-diff)/2, (sum+diff)/2);

first = false;

}

int main()

{

int cases;

scanf("%d", &cases);

for (int i = 0; i < cases; i++)

testcase();

delete a;

delete b;

return 0;

}