## 10032 - Tug of War

Moderator: Board moderators

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

### 10032 - Tug of War

Code: Select all

``````#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>

int main(){
int n, m, s;
bool a;

a = 1;

scanf( "%d", &n );

for ( int i = 0; i < n; i++ ){
memset( a, 0, 45002 * sizeof( bool ) );
a = 1;
int sum = 0;
scanf( "%d", &m );
for ( int j = 0; j < m; j++ ){
scanf( "%d", &s );
sum += s;
for ( int k = 45001; k >= s; k-- ){
a[k] |= a[k-s];
}
}

for ( int k = ( sum ) / 2 ; k >= 0; k-- ){
if ( a[k] ){ printf("%d %d\n", k, ( sum ) - k );
break;
}
}
}
}``````
I don't know what's wrong with this.. it works with most of the cases I've tried it with. Thanks in advance!

10153EN
Experienced poster
Posts: 148
Joined: Sun Jan 06, 2002 2:00 am
Location: Hong Kong
Contact:
I think you have not considered one of the constrains, as it stated:
the number of people on the two teams must not differ by more than 1
Try to take consideration into this constrain and it should be OK~ Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:
Hah! Ya, now I feel stupid. I guess reading isn't one of my best assets.. =)

I was thinking of another problem, I suppose..

hank
Experienced poster
Posts: 146
Joined: Mon Feb 04, 2002 2:00 am
Location: VCORE.

### 10032 Tug of War [WA,need test!]

hi~
I didn't find any bug.
I use Greedy Algorithm to use this problem.

Please give me some test data of this problem.
(I think it well be helpful~)
[c]
#include "stdio.h"
#include "stdlib.h"
#define MAX 10000
int man;
void solve(int n)
{
int i,j,k,p,amt=0,max,min;
int s=0,target,minof,index;
target=0;
for(i=1;i<=n;i++)
target+=man;
target*=10;
target/=2;
minof=MAX;
if(n%2==0) max=n/2;
else max=n/2+1;

for(amt=0;amt<max;){
for(j=1,index=0;j<=n;j++)
if( abs( ( s + man[j] ) * 10 - target ) < minof && man[j]!=-1 ){
minof=abs( ( s + man[j] ) * 10 - target );
index=j;
}
if( index ){
s+=man[index];
man[index]=-1;
amt++;
}else if((amt+1<max&&n%2==1) || (amt<max&&n%2==0) ){
min=MAX;
for(i=1;i<=n;i++)
if( man < min && man!=-1 ){ min=man; index=i; }
s+=man[index];
man[index]=-1;
amt++;
}else if(amt+1>=max){
break;
}
}
if(s<target/5-s)
printf("%d %d\n",s,target/5-s);
else
printf("%d %d\n",target/5-s,s);
}
void main()
{
int N,n;
int i,j,k;
scanf("%d",&N);
for(;N;N--){
scanf("%d",&n);
for(i=1;i<=n;i++)
scanf("%d",&man);
solve(n);
printf("\n");
}
}[/c]

turuthok
Experienced poster
Posts: 193
Joined: Thu Sep 19, 2002 6:39 am
Location: Indonesia
Contact:
Try input:

1

10
9
1
1
1
1
1
1
1
1
1

The output should be:

9 9

junjieliang
Experienced poster
Posts: 169
Joined: Wed Oct 31, 2001 2:00 am
Location: Singapore
Are you sure? I think there is somewhere in the problem that the groups must be divided into groups as close in numbers as possible. Hence the output should be 13 5 instead.

turuthok
Experienced poster
Posts: 193
Joined: Thu Sep 19, 2002 6:39 am
Location: Indonesia
Contact:
Oops, ... you're totally correct. I should have read the problem desc. more carefully ... Next time I post a comment, I'll try to solve the problem first ...

Sorry for the mistake, ...

-turuthok-

turuthok
Experienced poster
Posts: 193
Joined: Thu Sep 19, 2002 6:39 am
Location: Indonesia
Contact:

### 10032 - Tug of War

This is another interesting problem (http://acm.uva.es/p/v100/10032.html).

I recently solved it using straightforward logic that will have all possible weights info, and at the end look up the best subset of (n/2) people that has minimal weight-difference. However, it is pretty slow ... I got AC in about 2 seconds.

Can anybody give a hint about another faster approach ... ???

Thanks for all the attention -turuthok-
The fear of the LORD is the beginning of knowledge (Proverbs 1:7).

miras
Learning poster
Posts: 98
Joined: Sat Jun 14, 2003 1:45 pm

### 10032

i have got WA but i don't know why?

Can anyone help me?

it's my code
[pascal]var tab:Array[1..5000] of longint;
z:array[0..5000] of integer;
qw,how,sss,s,p,d,w,n,ile,a,q,srednia:longint;

begin

for sss:=1 to how do
begin
qw:=0;
s:=0;
p:=0;
d:=0;
n:=0;
ile:=0;
q:=0;
srednia:=0;
for a:=1 to 5000 do begin tab[a]:=0; z[a]:=0; end;
a:=0;

for a:=1 to ile do begin read(tab[a]); srednia:=srednia+tab[a]; end;
qw:=srednia;
srednia:=srednia div 2;

z:=1;

repeat
n:=n+1;

for q:=srednia+1 downto tab[n] do

if z[q-tab[n]]=1 then z[q]:=1;

until (n=srednia) ;

s:=srednia+1;

repeat
dec(s);
if z[s]=1 then begin p:=s; s:=1; end;

until s=1;

d:=qw-p;

if p>d then writeln(d,' ',p) else writeln(p,' ',d);
writeln;

end;

end.

thanks [/pascal]

miras
Learning poster
Posts: 98
Joined: Sat Jun 14, 2003 1:45 pm
Don't look at the last line!!!

PatrickM
New poster
Posts: 1
Joined: Sat Jul 19, 2003 1:23 pm

### 10032 WA

Code: Select all

``````#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>

using namespace std;

typedef vector<int>::reverse_iterator VI;

int main ()
{
int N, Num;

cin >> N;
for (int i=0; i<N; i++)
{
long equip1 = 0;
long equip2 = 0;
cin >> Num;
vector<int> gent(Num);
stack<int> SEquip1;
stack<int> SEquip2;
for (int j=0; j<Num; j++) cin >> gent[j];
sort(gent.begin(),gent.end());

for (VI p=gent.rbegin(); p!=gent.rend(); p++)
{
if (equip1>equip2)
{
equip2+=(*p);
SEquip2.push(*p);
}
else
{
equip1+=(*p);
SEquip1.push(*p);
}
}
// Equilibrem
while (abs((int)SEquip1.size() - (int)SEquip2.size())>1)
{
if (((int)SEquip1.size() - (int)SEquip2.size())>0)
{
SEquip2.push(SEquip1.top());
equip2+=SEquip1.top();
equip1-=SEquip1.top();
SEquip1.pop();
}
else
{
SEquip1.push(SEquip2.top());
equip1+=SEquip2.top();
equip2-=SEquip2.top();
SEquip2.pop();
}
}

if (equip1>equip2) cout << equip2 << " " << equip1 << endl;
else cout << equip1 << " " << equip2 << endl;
}
}
``````
can anyone tell me what's wrong with my code?

miras
Learning poster
Posts: 98
Joined: Sat Jun 14, 2003 1:45 pm
Patric read the text 3 times remember that f.e.
INPUT
400
200
100
100

output
500 300 _____________________
Made The FOrce BE With You

funkinthetrunk
New poster
Posts: 1
Joined: Mon Oct 20, 2003 5:31 am
Contact:

### 10032 Tug of War Wrong Answer

Given a number of players with their weights, create the most evenly weighted teams where the number of players on each team is equal or off by one.

Here's my code. I basically make the most evenly weighted teams and then check to see if they are within one of each other. If not, I fall back to the previous item and switch teams.

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int addweight(int , int , int , int, int, int *);
void insertion_sort(int *, int);

int main()
{
int numcases, numpeople, i, weighta, weightb, playersa, playersb;
int weights;

scanf("%i", &numcases);

while(numcases)
{
weighta = 0;
weightb = 0;
playersa = 0;
playersb = 0;

scanf("%i", &numpeople);

for(i = 0; i < numpeople; ++i)
scanf("%i", &weights);

insertion_sort(weights, i);

addweight(i - 1, weighta, weightb, playersa, playersb, weights);

/*for(i = 0; i < numpeople; ++i)
printf("%i ", weights);*/

--numcases;
}
return 0;
}

int addweight(int n, int weighta, int weightb, int playersa, int playersb, int *weights)
{
/*weightflag 1: a is smaller, 0: b is smaller*/
int stop, weightflag;

/*printf("%i: weighta:%i playersa:%i, weightb:%i playersb:%i\n", n, weighta, playersa, weightb, playersb);*/

if(n < 0)
{
if(abs(playersa - playersb) < 2)
{
if(weighta > weightb)
printf("%i %i\n", weightb, weighta);
else
printf("%i %i\n", weighta, weightb);

return 1;
}
else
return 0;
}

if(weighta < weightb)
{
/* printf("A is smaller\n");*/
weightflag = 1;
}
else
{
/*printf("B is smaller\n");*/
weightflag = 0;
}

if(weightflag)
stop = addweight(n - 1, weighta + weights[n], weightb, playersa + 1, playersb, weights);
else
stop = addweight(n - 1, weighta, weightb + weights[n], playersa, playersb + 1, weights);

if(stop)
return 1;

if(weightflag)
{
/*weighta -= weights[n];
--playersa;*/
stop = addweight(n - 1, weighta, weightb + weights[n], playersa, playersb + 1, weights);
}
else
{
/*weightb -= weights[n];
--playersb;*/
stop = addweight(n - 1, weighta + weights[n], weightb, playersa + 1, playersb, weights);
}

if(stop)
return 1;
else
return 0;

}

void insertion_sort(int *s, int n)
{
int i, j, temp;

for(i = 1; i < n; i++)
{
j = i;
while((j > 0) && (s[j] < s[j - 1]))
{
temp = s[j];
s[j] = s[j - 1];
s[j - 1] = temp;

j = j - 1;
}
}

return;
}

Input:
3

4
400
202
200
1

3
100
90
200

5
400
3
400
1
400

Output:
401 402
190 200
404 800

Emranul Hassan
New poster
Posts: 1
Joined: Thu Nov 06, 2003 8:57 am

### i dont know why i got wrong anser.

Is there any critical input.

code
/*
#include<stdio.h>
#define MAX 110
#define MAXNUM MAX*500
long ary[MAX],no,num;
long res[MAXNUM];
void init()
{
long i;
for(i=0;i<MAX;i++)
ary=0;
for(i=0;i<MAXNUM;i++)
res=-1;
res=0;
}
long calculate(long num,long sum)
{
long i,j;
for(j=0;j<num;j++)
for(i=sum;i>=0;i--)
if(res>=0 && res[i+ary[j]]==-1)
res[i+ary[j]]=res+1;
for(i=sum/2;i>0;i--)
{
if(num==1)
return 0;
if(num%2==1)
{
if(res==num/2 || res==num/2+1)
return i;
}
else
if(res==num/2)
return i;

}
return 0;

}
void main()
{
long i,j,sum,temp;
scanf("%ld",&no);
for(i=0;i<no;i++)
{
init();
sum=0;
scanf("%ld",&num);
for(j=0;j<num;j++)
{
scanf("%ld",&ary[j]);
sum+=ary[j];
}
temp=calculate(num,sum);
printf("%ld %ld\n\n",temp,sum-temp);
}
}
*/

Maarten
Experienced poster
Posts: 108
Joined: Sat Sep 27, 2003 5:24 pm
( 1 ) can you use formatting tags to post code?
( 2 ) can you explain your algorithm?