Ok, I am posting this here since there seems to be so many people at this forum who love problem solving and a good challenge. First off, this is not homework. I am studying for a programming competition coming up and am doing so problems I found at a website. I wanted to start off on an easy one, but for the life of me I can't understand why this one won't work. I keep submitting it but I keep getting back from the judge that for some test data my algorithm returns the wrong answer - but it won't say which test data and everything I can think of gives a correct answer. The problem statement is here.

Basically this is my algorithm. First find out what the average amount is, rounded down. Then I cycle through all of the amounts, and if the amount is less than the average, I add the difference to the LESS pile, and if the amount is more than the average, then I add the difference to the MORE pile. If I had to round down when I first calculated the difference, then I add one to the average when I do the difference between a pile that is greater and the average.

Now I figure that the greater of the two amounts is the minimum amount of money that needs to be transferred. Like for example if the LESS pile is $2.00 and the MORE pile is $2.01, then the minimum amount of money transfered is $2.01 since if only 2 dollars were transferred, then the MORE people wouldn't be within one cent. So I always return the greater of the two numbers. But I get the wrong answer even though every thing I have tried has given me a correct answer!

Can anyone at all think of a set of data that breaks my algorithm or a logical reason why it is flawed? This is driving me nuts!

Here is the code:

Code:`#include<iostream>`

#include<string>

#include<vector>

using namespace std;

int max(int x, int y) {if (x>y) return x; else return y;}

int min(int x, int y) {if (x<y) return x; else return y;}

int main()

{

while (1)

{

int num; // number of students

int x;

int total=0; // total amount spent in pennies

int more=0; // amount over the average spent in pennies

int less=0; // amount under the average spent in pennies

bool round=false; // average came out evenly or not

vector<int> vecF; // vector holding each amount paid

cin>>num;

if (!num)

break;

for (x=0; x<num; x++)

{

double d;

cin>>d;

vecF.push_back(int(d*100));

total+=(vecF[x]);

}

if (total%num!=0)

round=true;

total/=num;

for (x=0; x<vecF.size(); x++)

{

if (round && vecF[x]>total+1)

more+=(vecF[x]-(total+1));

else if (!round && vecF[x]>total)

more+=(vecF[x]-total);

else

less+=(total-vecF[x]);

}

less=max(less,more);

cout<<"$"<<less/100<<".";

if (less%100<10)

cout<<"0";

cout<<less%100<<endl;

}

return 0;

}