10137 - The Trip

[Observer]

Your job is to compute, from a list of expenses, the minimum amount of money that must change hands in order to equalize (within a cent) all the students' costs.

Clearly, 0.01 != 0.03, within a cent or not. If your AC code prints 0.00, then I think the judge input is too weak.

[Jan]

You are right. The judge data is weak indeed. But then what is your procedure.

I found the average, round it, and a = sum(greateritem-avg), b=(avg-smallerItem).

Then printed min(a,b) with rounding..

May be I have to go through the problem again....

[paulmcvn]

Yep, I've just got AC although my program outputs $0.00 for the above case!

So what is the correct algorithm?

[ahmad_h]

I have looked all over the forum and I can't understand why am I getting a WA on this one The method I use:
First of all the thing to understand is that by the end of the day (after exchanging money) all friends will have spent an amount which is within 0.01 of all the other amounts. So we just need to calculate the average expenditure ... and then calculate the cents each person spending more will receive to get to the (ceil) of the avg...and then calculate the cents each person spending less will give to get to the (floor) of the avg. E.g. if the avg is 9.0155 the ceil would be 9.02 and floor would be 9.01. I get the answer by taking the largest between the total cents taken and total cents given.

I have checked all the test cases given on the forums and my code works fine for all of them....but still WA

Code:

Code: Select all

#include <stdio.h>

int main()
{
   unsigned int i, no_friends;
   double total_spent;
   double total_disparity_give;
   double total_disparity_take;
   double avg_spent;
   double avg_spent_ceil, avg_spent_floor;
   double expenditure[1000];

   while( scanf( "%d", &no_friends ) != EOF && no_friends != 0 )
   {
      total_spent = 0.0;
      total_disparity_give = 0.0;
      total_disparity_take = 0.0;

      for( i = 0; i < no_friends; i++ )
      {
         sscanf( "%Lf", &(expenditure[i]) );
         total_spent += expenditure[i];
      }

      avg_spent = (float)(total_spent / no_friends);
      avg_spent_floor = (float)((int)(avg_spent * 100)) / 100;
      avg_spent_ceil = avg_spent > avg_spent_floor ? avg_spent_floor + 0.01 : avg_spent_floor ;

      for( i = 0; i < no_friends; i++ )
      {
         if( expenditure[i] > avg_spent )
            total_disparity_take += expenditure[i] - avg_spent_ceil;
         else
            total_disparity_give += avg_spent_floor - expenditure[i];
      }

      printf( "$%.2f\n", total_disparity_take > total_disparity_give ? total_disparity_take : total_disparity_give );
   }

   return 0;
}

HELP...SOS

[Mata]

hi, im getting wrong answer in this problem, i've tried the sample input in the forums and it is ok, what could be wrong? .
here is my code

Code: Select all

#include <iostream>
int main()
{
	long long n=0;
	while(scanf("%ld",&n)==1&&n>0)
	{
		double tempo=0,low=0,high=0,t2=0;
		long long cents[n], total=0,x=0,avg=0,mod=0;
		while(x<n)
		{
			scanf("%lf",&tempo);
			cents[x]=(long long)(tempo*100);
			t2=((double)cents[x])/100;
			if(t2<tempo)
				cents[x]++;
			total+=cents[x];
			x++;
		}
		mod=total%n;
		if(mod==0)
			avg=total/n;
		else
			avg=((total-mod)/n);
		x=0;
		while(x<n)
		{
			if(n>0&&cents[x]>avg+1)
				high+=cents[x]-avg-1;
			else if(n==0&&cents[x]>avg)
				high+=cents[x]-avg;
			else if(cents[x]<avg)
				low+=avg-cents[x];
			x++;
		}
		if(high>low)
			printf("$%.2lf\n",high/100);
		else
			printf("$%.2lf\n",low/100);
	}
	return 0;
}

[deadangelx]

10137 I got AC

and Look at this code!!

the important thing I dont know why is about elist vector.
I produced 4 possible values and sort them.
The correct answer is always in the 2nd position.
So, I got AC.
Could anyone tell me that this is a coincidence or not, thx.

Code: Select all

/*****************************/
/* Problem 10137             */
/* Author: Chien-Mao Chen    */
/* Last Modified: 2008/01/29 */
/*****************************/

#include <iostream>
#include <iomanip>
#include <vector>
using namespace std;

template <class elemType>
inline void quicksort(vector<elemType> &a, int left, int right)
{     
  int i,j,max;
  elemType s;
  if(left<right)
  {
    s=a[left];
    i=left;
    max=j=right+1;
    while(1)
    {
      while((i+1)<max && a[++i] < s);
      while((j-1)>-1 && a[--j] > s);
      if(i>=j) break;
      swap(a[i],a[j]);
    }
    a[left]=a[j];
    a[j]=s;
    quicksort(a,left,j-1);
    quicksort(a,j+1,right);
  }
}

int main(void)
{
  int n;              //n students
  double exps;        //expenses
  double s_exps;     //shared expenses
  double ts_exps;    //temp for shared expenses
  
  int co,cb;  //count over avg, count below avg
  
  vector<double> e;  //expenses for vector
  vector<double> elist(4);
  
  while((cin>>n)&&n)
  {
    e.clear();
    s_exps=0.0;
    for(int i=0; i<n; ++i)
    {
      cin>>exps;
      e.push_back(exps);
      s_exps+=exps;
    }
    
    s_exps/=n;
    s_exps=static_cast<int>(s_exps*100+1e-9)/100.0;
    
    //count over and below avg
    co=cb=0;
    for(int i=0; i<n; ++i)
    {
      if(e.at(i)>s_exps)
        ++co;
      else if(e.at(i)<s_exps)
        ++cb;
    }
    
    //another candidate of shared expenses
    ts_exps=s_exps+1e-2; 

    cout<<"$";
    cout<<fixed<<setprecision(2);

    if(co>cb&&!cb)
    {
      for(int i=0; i<n; ++i)
          if(e.at(i)>ts_exps)
          {
            cout<<(e.at(i)-ts_exps)/2;
            break;
          }
    }
    else if(co<cb&&!co)
    {
      for(int i=0; i<n; ++i)
          if(e.at(i)<ts_exps)
          {
            cout<<((e.at(i)-ts_exps)*-1)/2;
            break;
          }
    }
    else
    {
      elist.clear();
      elist[0]=elist[1]=0.0;
      elist[2]=elist[3]=0.0;
      for(int i=0; i<n; ++i)
      {
          if(e.at(i)<ts_exps)
            elist[0]+=((e.at(i)-ts_exps)*-1);
          else if(e.at(i)>ts_exps)
            elist[1]+=(e.at(i)-ts_exps);
          if(e.at(i)<s_exps)
            elist[2]+=((e.at(i)-s_exps)*-1);
          else if(e.at(i)>s_exps)
            elist[3]+=(e.at(i)-s_exps);
      }
      cout<<elist[0]<<" "<<elist[1]<<" "<<elist[2]<<" "<<elist[3]<<endl;
        quicksort(elist,0,3);
        cout<<elist[1];
    }
    cout<<endl;
  }
  
  return 0;
}

[jud]

The correct outputs for the inputs:

Code: Select all

3
10.00
20.00
30.00
4
15.00
15.01
3.00
3.01
3
6.17
5.00
4.03
12
123.12
6.13
9.44
89.08
278.78
223.78
78.45
912.89
554.76
547.57
1781.89
907.07
2
4.99
15.00
1
10.00
15
0.01
0.01
0.01
0.01
0.01
0.01
0.01
0.01
0.01
0.01
0.01
0.01
0.01
0.01
0.03
5
5000.00
11.11
11.11
11.11
11.11
15
0.01
0.03
0.03
0.03
0.03
0.03
0.03
0.03
0.03
0.03
0.03
0.03
0.03
0.03
0.03
4
25.00
25.00
25.00
28.00
3
10.01
15.25
18.96
4
25.03
25.00
25.00
25.00
0

should be:

Code: Select all

...

Check it out, so you may find out what you're doing wrong.

your output isn't correct. i've tried it with the same output and got WA. after a better rounding-function (floor(x+0.5)) it gets AC.

output should be:

Code: Select all

$10.00
$11.99
$1.10
$2407.09
$5.00
$0.00
$0.02
$3991.11
$0.02
$2.25
$4.73
$0.02

good luck

[deadangelx]

thx for ur test cases

But, di u see the "cout<<" in my code

Code: Select all

cout<<elist[0]<<" "<<elist[1]<<" "<<elist[2]<<" "<<elist[3]<<endl;

I just let everyone to see clear

so I've never removed it.

If u try to remove this code and send it to jduge now, it will be AC.

I just sent again today.

The correct outputs for the inputs:

Code: Select all

3
10.00
20.00
30.00
4
15.00
15.01
3.00
3.01
3
6.17
5.00
4.03
12
123.12
6.13
9.44
89.08
278.78
223.78
78.45
912.89
554.76
547.57
1781.89
907.07
2
4.99
15.00
1
10.00
15
0.01
0.01
0.01
0.01
0.01
0.01
0.01
0.01
0.01
0.01
0.01
0.01
0.01
0.01
0.03
5
5000.00
11.11
11.11
11.11
11.11
15
0.01
0.03
0.03
0.03
0.03
0.03
0.03
0.03
0.03
0.03
0.03
0.03
0.03
0.03
0.03
4
25.00
25.00
25.00
28.00
3
10.01
15.25
18.96
4
25.03
25.00
25.00
25.00
0

should be:

Code: Select all

...

Check it out, so you may find out what you're doing wrong.

your output isn't correct. i've tried it with the same output and got WA. after a better rounding-function (floor(x+0.5)) it gets AC.

output should be:

Code: Select all

$10.00
$11.99
$1.10
$2407.09
$5.00
$0.00
$0.02
$3991.11
$0.02
$2.25
$4.73
$0.02

good luck

[jud]

got it. but it must not be such a complicated code including quicksort and stuff. also simple arrays will do the job efficiently. just compute the minimum of the summed differences of the values over/less the avg.

keep ur code as simple as possible, but not simpler.

regards

[rtu]

This problem really tripped me two days. After reading the previous post, I figured out that it is better not to round down the average at the first time. Then like the other said, I choose the maximum between the sum diff of the greater than average and the lesser than average. We should always take floor, because you only can exchange within one cent . At last you see Solved

[VarunGupta]

I tested following code on my local machine for given and some other test cases but received "Wrong Answer" response from the Online Judge,

Code: Select all

#include <iostream>
#include <vector>

using namespace std;

int main()
{
 	int n;
	while(cin >> n)
	{
	 		  if (n == 0)
	 		  {
			   	 	break;
			  }
 	float av, s = 0.00, rs = 0.00;
 	vector <float> p(n);
 	
 	for (int i = 0; i < n; i ++)
 	{
	 	  cin >> p[i];
	 	  s += p[i];
	}
	av = s / n;
	av -= ((av * 100) - int(av * 100)) / 100.00;
	
	for (int i = 0; i < n; i ++)
 	{
	 	  if (p[i] < av)
	 	  {
		   	 	   rs += av - p[i];
		  }
	}
	 	  cout << "$" << rs << endl;
	}
 	return 0;
}

Can someone please point me to the issue?

[VarunGupta]

Some of the test cases can be ambiguous. eg.

Code: Select all

3
6.17
5.00
4.03

In this case the average comes to be 5.066666...
Now, if we round it of to 5.06 the answer comes to be $1.09 and if the average is rounded to 5.07, answer will be $1.11. But $1.10 is the answer is listed in the test cases posted above (3rd case in the list).

Is there any resolution of this issue?

Code: Select all

int main()
{
 	int n;
	while(cin >> n)
	{
	 		  if (n == 0)
	 		  {
			   	 	break;
			  }
			  vector <int> p(n);
			  int s = 0, rs = 0, av;
			  
			  for (int i = 0; i < n; i ++)
			  {
			   	  double t;
				  cin >> t;
				  t *= 100;
				  p[i] = int(t);
				  s += p[i];
			  }
			  av = floor((double(s) / double(n)));
			  
			  for (int i = 0; i < n; i ++)
			  {
			   	  if (p[i] < av)
				  {
				   	 	   rs += av - p[i];
				  }
			  }
			  if (rs % 100 == 0)
			  {
			   	 	 cout << "$" << rs / 100 << ".00" << endl;
			  }
			  else if (rs % 100 < 10)
			  {
			   	   cout << "$" << rs / 100 << ".0" << rs % 100 << endl;
			  }
			  else
			  {
			   	  cout << "$" << rs / 100 << "." << rs % 100 << endl;
			  }
	}
 	return 0;
}

[DD]

I tested following code on my local machine for given and some other test cases but received "Wrong Answer" response from the Online Judge,

Code: Select all

#include <iostream>
#include <vector>

using namespace std;

int main()
{
int n;
while(cin >> n)
{
if (n == 0)
{
break;
}
float av, s = 0.00, rs = 0.00;
vector <float> p(n);

for (int i = 0; i < n; i ++)
{
cin >> p[i];
s += p[i];
}
av = s / n;
av -= ((av * 100) - int(av * 100)) / 100.00;

for (int i = 0; i < n; i ++)
{
if (p[i] < av)
{
rs += av - p[i];
}
}
cout << "$" << rs << endl;
}
return 0;
}

Can someone please point me to the issue?

I think your program only calculate the distance of people who pay less. You should also consider the people who pay more in this trip.
BTW, it may be dangerous to use float in this problem, I use double to got A.C.

[mak(cse_DU)]

The correct outputs for the inputs:

Code: Select all

3
10.00
20.00
30.00
4
15.00
15.01
3.00
3.01
3
6.17
5.00
4.03
12
123.12
6.13
9.44
89.08
278.78
223.78
78.45
912.89
554.76
547.57
1781.89
907.07
2
4.99
15.00
1
10.00
15
0.01
0.01
0.01
0.01
0.01
0.01
0.01
0.01
0.01
0.01
0.01
0.01
0.01
0.01
0.03
5
5000.00
11.11
11.11
11.11
11.11
15
0.01
0.03
0.03
0.03
0.03
0.03
0.03
0.03
0.03
0.03
0.03
0.03
0.03
0.03
0.03
4
25.00
25.00
25.00
28.00
3
10.01
15.25
18.96
4
25.03
25.00
25.00
25.00
0

should be:

Code: Select all

...

Check it out, so you may find out what you're doing wrong.

your output isn't correct. i've tried it with the same output and got WA. after a better rounding-function (floor(x+0.5)) it gets AC.

output should be:

Code: Select all

$10.00
$11.99
$1.10
$2407.09
$5.00
$0.00
$0.02
$3991.11
$0.02
$2.25
$4.73
$0.02

good luck

The output is also wrong.............................................................
The Actual output is below:

Code: Select all

$10.00
$11.99
$1.10
$2407.09
$5.00
$0.00
$0.01............................//here was error
$3991.11
$0.01...........................//here was error
$2.25
$4.73
$0.02

[tomtom85]

I dont understand whats happening (yea i know you have read this many times but). I got AC on http://www.programming-challenges.com with this code and here i get WA. This is like uber odd. here is the code if someone is willing to help.

Code: Select all

#include <stdio.h>
#include <math.h>
int main(){
    
    int people,x;
    double su,sump,sumn,values[1001],media;
    scanf("%d\n",&people);
    while(people){    
            media = sump = sumn = 0;
        
            for(x=0;x<people;x++){
                scanf("%lf",&su);
                values[x] = floorf(su*100)/100;
                media += su;
            }
            media = (media/people);

            for(x=0;x<people;x++){
                if(values[x] <= media){
                    sumn -= ceilf((values[x]-media)*100)/100;
                }else{
                    sump += floorf((values[x]-media)*100)/100;
                }
            }
              printf("$%.2lf\n",sumn > sump ? sumn : sump );
        scanf("%d\n",&people);
    }        
    return 0;
}