# Tug of War

Tug of War

Tug of war is a contest of brute strength, where two teams of people pull in opposite directions on a rope. The team that succeeds in pulling the rope in their direction is declared the winner.

A tug of war is being arranged for the office picnic. The picnickers must be fairly divided into two teams. Every person must be on one team or the other, the number of people on the two teams must not differ by more than one, and the total weight of the people on each team should be as nearly equal as possible.

The first line of each case contains n, the number of people at the picnic. Each of the next n lines gives the weight of a person at the picnic, where each weight is an integer between 1 and 450. There are at most 100 people at the picnic.

For each test case, your output will consist of a single line containing two numbers: the total weight of the people on one team, and the total weight of the people on the other team. If these numbers differ, give the smaller number first.

``````3
100
90
200

``````

``190 200``

``````#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n,w[103],sum,ans,l,r;
bool dp[45005][103];
int main()
{
memset(dp, 0, sizeof(dp));
scanf("%d", &n);
sum=0;
for(int i=1;i<=n;i++)scanf("%d",&w[i]),sum+=w[i];
dp[0][0]=dp[0][101]=1;
for(int i=1;i<=n;++i)
for(int j=sum;j>=w[i];--j)
if(dp[j-w[i]][101])
{
dp[j][101]=1;
for(int k=0;k<n;k++)
if(dp[j-w[i]][k])dp[j][k+1]=1;
}
ans=sum/2;
while(!(dp[ans][101]&&(dp[ans][n/2]||dp[ans][(n+1)/2])))--ans;
printf("%d %d\n",ans,sum-ans);
return 0;
}``````

``````#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n,w[103],sum,ans,l,r;
bool dp[45005][103];
int main()
{
memset(dp, 0, sizeof(dp));
scanf("%d", &n);
sum=0;
for(int i=1;i<=n;i++)scanf("%d",&w[i]),sum+=w[i];
dp[0][0]=dp[0][101]=1;
for(int i=1;i<=n;++i)
for(int j=sum;j>=w[i];--j)
if(dp[j-w[i]][101])
{
dp[j][101]=1;
for(int k=0;k<n;k++)
if(dp[j-w[i]][k])dp[j][k+1]=1;
}
ans=sum/2;
while(!(dp[ans][101]&&(dp[ans][n/2]||dp[ans][(n+1)/2])))--ans;
printf("%d %d\n",ans,sum-ans);
return 0;
}``````