I am working on the UVa problem 10032 - Tug of War, where I'm given the time constraint of 3 seconds to solve the problem. I have pasted the criteria for the problem below.
A tug of war is to be arranged at the local office picnic. For the tug of war, the picnickers must be divided into two teams. Each person must be on one team or the other; the number of people on the two teams must not differ by more than 1; the total weight of the people on each team should be as nearly equal as possible.
Input
The input begins with a single positive integer on a line by itself indicating the number of the cases following, each of them as described below. This line is followed by a blank line, and there is also a blank line between two consecutive inputs.
The first line of input contains n the number of people at the picnic. n lines follow. The first line gives the weight of person 1; the second the weight of person 2; and so on. Each weight is an integer between 1 and 450. There are at most 100 people at the picnic.
Output
For each test case, the output must follow the description below. The outputs of two consecutive cases will be separated by a blank line.
Your output will be a single line containing 2 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 lesser first.
Sample Input
1
3
100
90
200
Sample Output
190 200
My code is here
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include <iostream>
using namespace std;
int n, m, a, b, c, d, low, hi, turn, p[2], q[2], z[100] = {0};
void BubbleSort()
{
int i, j, flag = 1; // set flag to 1 to start first pass
int temp; // holding variable
int numLength = m + 1;
for(i = 1; (i <= numLength) && flag; i++)
{
flag = 0;
for (j=0; j < (numLength -1); j++)
{
if (z[j+1] < z[j]) // ascending order simply changes to <
{
temp = z[j]; // swap elements
z[j] = z[j+1];
z[j+1] = temp;
flag = 1; // indicates that a swap occurred.
}
}
}
return; //arrays are passed to functions by address; nothing is returned
}
/*
*
*/
int main(int argc, char** argv) {
cin >> n; //read in how many test cases
for(int i = 0; i <n; i++)
{
cin >> m; //read in how many persons
for(int j = 1; j <= m; j++)
{
cin >> z[j]; //read in the weight of the persons and put them in an array
}
BubbleSort(); //sort the persons
low = 1;
hi = m;
p[0] = 0;
p[1] = 0;
q[0] = 0;
q[1] = 0;
if(m == 1) //in case there is only 1
{
p[0] += z[m];
p[1] ++;
}
else
{
while((hi - low) >= 0) //while there are still people left
{
if((p[0] == q[0]) && ((hi - low) >= 1)) //case where the two ropes are equal
{
p[0] += z[hi]; //add the heaviest person to p
p[1] ++;
hi --; //subtract the heaviest person
q[0] += z[hi]; //add the heaviest person to q
q[1] ++;
hi --; //subtract the heaviest person
}
else if((p[0] > q[0]) && ((hi - low) >= 1)) //case where p>q
{
p[0] += z[low]; //add the lightest person to p
p[1] ++;
low ++; //take out the lightest person
q[0] += z[hi]; //add the heaviest person to q
p[1] ++;
hi --; //subtract the heaviest person
}
else if((p[0] < q[0]) && ((hi - low)) >= 1) //case where p<q
{
p[0] += z[hi]; //add the heaviest person to p
p[1] ++;
hi --; //subtract the heaviest person
q[0] += z[low]; //add the lightest person to p
q[1] ++;
low ++; //take out the lightest person
}
else if((hi - low) == 0) //case where there is an odd number of people
{
if(p[0] < q[0])
{
p[0] += z[hi]; //add the heaviest person to p
p[1] ++;
hi --; //subtract the heaviest person
}
if(p[0] > q[0])
{
q[0] += z[hi]; //add the heaviest person to q
q[1] ++;
hi --; //subtract the heaviest person
}
}
}
}
if(p[0] < q[0]) //print statements
{
cout << p[0] << " " << q[0] << endl << endl;
}
else
{
cout << q[0] << " " << p[0] << endl << endl;
}
}
return 0;
}I don't know why, but the automatic grader tells me I am exceeding the time limit, which one of the possibilities there is an infinite loop. I can't seem to make it error out with any of the test cases I have been able to come up with. If there is anyone out there that can find a test case that does this, or can point out where I have made a mistake, I would be greatly appreciated.
Thanks
Aaron