-
February 10th, 2010, 04:47 AM
#1
Team selection
TEAM SELECTION PROBLEM
One of the cherished customs of my childhood was choosing up sides for a cricket game. We did it this way: The two bullies of our gully would appoint themselves captains of the opposing teams, and then they would take turns picking other players. On each round, a captain would choose the most capable (or, towards the end, the least inept) player from the pool of remaining candidates, until everyone present had been assigned to one side or the other. The aim of this ritual was to produce two evenly matched teams and, along the way, to remind each of us of our precise ranking in the neighbourhood pecking order.
We all believed this was the fairest process, but does it ensure the fairest selection of players with evenly matched teams? We believed so, but then there were times when, as the game progressed we realized that the other team was stronger than ours and may be an exchange of a couple of players between the teams would have made them balanced. That scope of improvement seemed to be there...
Here, we need to find a way to create two evenly balanced teams for any game(or as evenly balanced as possible considering the strength of each player). A set of players must be divided into two teams. Each player must be on one team or the other; the number of player on the two teams must not differ by more than 1; each player will have a skill-point associated with him. The total skill-points of the players on each team should be as nearly equal as possible.(The absolute difference of the sum of skill-points of players in each team should be the least).
Input
The first line of input will contain the number of test cases 'T'(1<=T<=100). This is followed by 'T' test cases. Each test case starts with a blank line, followed by N, the total number of players. N lines will follow with the first line giving the skill-point of person 1; the second line, the skill-point of person 2; and so on. Each skill-point shall be an integer between 1 and 450. There shall be at most 100 players in all(1<=N<=100).
Output
Your output should be exactly '2T-1' lines. The output for each test case should be followed by a blank line, except the output for the last test case. Each odd numbered line should contain 2 numbers: the total skill-points of the players on one team, and the total skill-points of the players on the other team. Print the smaller sum first.
Example
Input:
4
3
90
200
100
10
2
3
10
5
8
9
7
3
5
2
10
1
1
1
1
1
1
1
1
1
9
8
87
100
28
67
68
41
67
1
Output:
190 200
27 27
5 13
229 230
Code:
Code:
#include<iostream>
#include<stdio.h>
static int swapi,swapj,tries;
int main()
{
static int t,result1[100],result2[100],k;
int i,j,temp,x,y;
int sum(int[],int);
int abs1(int);
void findfirstswap(int,int[],int[]);
scanf("%d",&t);
for(k=0;k<t;k++)
{
static int no;
static int a[100];
static int b[100];
printf("\n");
scanf("%d",&no);
for(i=0;i<100;i++)
a[i]=0;
for(i=0;i<no;i++)
scanf("%d",&a[i]);
for(j=0;j<no;j++)
{
for(i=0;i<(no-1);i++)
{
if(a[i]>a[i+1])
{
temp=a[i];
a[i]=a[i+1];
a[i+1]=temp;
}
}
}
j=0;
if((no%2)!=0)
no=no+1;
for(i=(no/2);i<no;i++)
{
b[j]=a[i];
a[i]=0;
j++;
}
findfirstswap(no,a,b);
while(swapi!=-1 && swapj!=-1 && tries<100)
{
x=a[swapi];
y=b[swapj];
a[swapi]=y;
b[swapj]=x;
findfirstswap(no,a,b);
}
if( sum(a,no) < sum(b,no) )
{
result1[k]=sum(a,no);
result2[k]=sum(b,no);
}
else
{
result1[k]=sum(b,no);
result2[k]=sum(a,no);
}
}
for(i=0;i<t;i++)
{
printf("%d %d",result1[i],result2[i]);
if(i!=(t-1))
printf("\n\n");
}
}
int sum(int a[],int no)
{
int i,sum=0;
for(i=0;i<(no/2);i++)
sum=sum+a[i];
return sum;
}
int abs1(int a)
{
if(a<0)
a=a*-1;
return a;
}
void findfirstswap(int no,int a[],int b[])
{
int diff=0,i,j,x,y,newdiff=0;
swapi=-1;
swapj=-1;
diff=sum(a,no)-sum(b,no);
if(diff==0)
return;
for(i=((no/2)-1);i>=0;i--)
{
for(j=0;j<=((no/2)-1);j++)
{
tries=tries+1;
x=a[i];
y=b[j];
newdiff=abs1(diff-(2*x)+(2*y));
if(newdiff<abs1(diff))
{
swapi=i;
swapj=j;
return;
}
}
}
return;
}
Above code works fine at my pc but shows error at online judge of codechef.Pls help asap as i am running short of time.Any help would be deeply appreciated
Last edited by Marc G; February 10th, 2010 at 05:01 AM.
Reason: Added code tags
-
February 10th, 2010, 05:51 AM
#2
Re: Team selection
What kind of error do you have? Do you have messages? Does your program crash?
Where is located your error? On a particular line? After a particular time?
In your code, you don't check the limits of your a and b arrays. If no is greater than 99 (yes 99, not 100, because the index starts at 0), then you can go beyond the boundaries.
-
February 10th, 2010, 08:06 AM
#3
Re: Team selection
Even if i take care of limits it is giving error and codechef does not tell line of error or so
-
February 10th, 2010, 08:35 AM
#4
Re: Team selection
Pls reply asap its really urgent.
-
February 10th, 2010, 08:58 AM
#5
Re: Team selection
Originally Posted by payalgodhani
it is giving error
What error? A crash? A freeze? A message? A wrong output? Describe what you see, otherwise do we have to guess?
-
February 10th, 2010, 09:44 AM
#6
Re: Team selection
No it is just saying Wrong Answer.Nothing else.So we have to guess what the error is.Pls reply asap i am running out of time.
Tags for this Thread
Posting Permissions
- You may not post new threads
- You may not post replies
- You may not post attachments
- You may not edit your posts
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|