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; }