Programming Problem Set #Team Split

Description

You want to split some people into two teams to play a game. In order to make the split, you first designate two team captains who take alternate turns selecting players for their teams. During each turn, the captain selects a single player for his team. Since each captain wants to make the strongest possible team, he will always select the best available player. The players have strengths, which are given in the input as list of integers strengths, where higher numbers indicate better players. After all the players have been selected, the team strength is computed as the sum of the strengths of the players on that team.

For example, if strengths={5,7,8,4,2}, then the first captain selects the player with strength 8 for his team, the second captain gets the player with strength 7, the first gets the one with strength 5, the second the one with strength 4, and the last one (strength 2) goes to the first team. The first team now has a total strength 8+5+2=15, and the second team has strength 7+4=11.

Output the absolute strength difference between the two teams. For the example above you should return 4 (=15-11).

Input Format

The first line contains an integer N (1 <= N <= 50). The next line contains N space-separated integers strengths (1 <= strength[i] <= 1000).

Output Format

An integer, the difference of strength between two teams.

 

Sample Input 1

5
5 7 8 4 2

Sample Output 1

4

Note

The example from the problem statement.

 

Sample Input 2

1
100

Sample Output 2

100

Note

A boring game with only one player. The second team has strength 0 (no players).

Sample Input 3

2
1000 1000

Sample Output 3

0

Note

Both teams with equal strength.

Sample Input 4

4
9 8 7 6

Sample Output 4

2

Sample Input 5

6
1 5 10 1 5 10

Sample Output 5

0

Sample Input 6

50
824 581 9 776 149 493 531 558 995 637 394 526 986 548 344 509 319 37 790 491 479 34 776 321 258 851 711 365 763 355 386 877 596 96 151 166 558 109 874 959 845 181 976 335 930 22 78 120 907 584

Sample Output 6

478

Code Solution

</pre>
<pre>#include <stdio.h>
#include <stdlib.h>

int main()
{
    int N,i,j, pos,a,x;

    scanf("%d",&N);
    if(N>=1 && N <=50){
        long int kuat[N], temp = 0, result1= 0, result2=0;
        a = 0;
         while (a < N) {
                if (scanf("%d", &x) != 1) break;
                kuat[a] = x;
                 if (!(kuat[a] >=1 &&kuat[a] <=1000 )){
                        return 0;
                 }
                a++;
            }
            for(i=0;i<N-1;i++){
                pos=i;
                for(j=i+1;j<N;j++){
                    if(kuat[j]>kuat[pos]){
                        pos=j;
                    }
                }
                if (pos!=i){
                    temp=kuat[pos];
                    kuat[pos]=kuat[i];
                    kuat[i]=temp;
                }
            }
            for(i=0;i<N;i++){
                if(i%2 == 0){
                    result1 += kuat[i];
                }
                else{
                    result1 -= kuat[i];
                }
            }
            printf("%d\n",result1);
    }
    return 0;
}</pre>
<pre>