10032 - Tug of War

[Larry]

Code: Select all

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

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

  a[0] = 1;

  scanf( "%d", &n );
  
  for ( int i = 0; i < n; i++ ){
    memset( a, 0, 45002 * sizeof( bool ) );
    a[0] = 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]

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]

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]

hi~
I always got wrong answer!
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[120];
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]

Try input:

1

10
9
1
1
1
1
1
1
1
1
1

The output should be:

9 9

[junjieliang]

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]

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]

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-

[miras]

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




readln(how);
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;

readln;

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



z[0]:=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]

Don't look at the last line!!!

[PatrickM]

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?
some tests please!!

[miras]

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]

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[100];

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]

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]=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]

( 1 ) can you use formatting tags to post code?
( 2 ) can you explain your algorithm?