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