10137 - The Trip

All about problems in Volume 101. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Post by Observer » Sat Sep 08, 2007 6:47 pm

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.
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Sat Sep 08, 2007 8:35 pm

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....
Ami ekhono shopno dekhi...
HomePage

paulmcvn
New poster
Posts: 34
Joined: Sat Nov 13, 2004 12:15 pm

Post by paulmcvn » Sun Sep 09, 2007 1:36 pm

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

So what is the correct algorithm?

ahmad_h
New poster
Posts: 5
Joined: Wed Mar 23, 2005 1:27 pm

10137 - The Trip

Post by ahmad_h » Sat Nov 17, 2007 7:14 pm

I have looked all over the forum and I can't understand why am I getting a WA on this one :oops: 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 :x

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

User avatar
Mata
New poster
Posts: 18
Joined: Mon Dec 17, 2007 11:35 pm
Location: Queretaro
Contact:

Wa

Post by Mata » Wed Jan 09, 2008 2:05 am

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
New poster
Posts: 32
Joined: Tue Feb 13, 2007 1:31 pm

coincidence or not?!

Post by deadangelx » Thu Jan 31, 2008 2:55 am

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
New poster
Posts: 4
Joined: Mon Jan 28, 2008 7:24 pm

Re: Correct outputs...

Post by jud » Tue Feb 05, 2008 11:35 pm

zxul767 wrote: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
New poster
Posts: 32
Joined: Tue Feb 13, 2007 1:31 pm

Re: Correct outputs...

Post by deadangelx » Thu Feb 07, 2008 8:07 am

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.
jud wrote:
zxul767 wrote: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
New poster
Posts: 4
Joined: Mon Jan 28, 2008 7:24 pm

Post by jud » Thu Feb 07, 2008 4:18 pm

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
New poster
Posts: 1
Joined: Thu Jun 12, 2008 9:15 pm

Re: 10137 - The Trip

Post by rtu » Fri Jun 13, 2008 12:55 am

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 :D . At last you see Solved :wink:

VarunGupta
New poster
Posts: 2
Joined: Thu Jul 03, 2008 9:10 am

Re: 10137 - The Trip

Post by VarunGupta » Thu Jul 03, 2008 12:58 pm

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
New poster
Posts: 2
Joined: Thu Jul 03, 2008 9:10 am

Re: 10137 - The Trip

Post by VarunGupta » Tue Jul 15, 2008 3:08 pm

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
Experienced poster
Posts: 145
Joined: Thu Aug 14, 2003 8:42 am
Location: Mountain View, California
Contact:

Re: 10137 - The Trip

Post by DD » Sun Nov 16, 2008 4:33 am

VarunGupta wrote: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. :wink:
BTW, it may be dangerous to use float in this problem, I use double to got A.C.
Have you ever...
  • Wanted to work at best companies?
  • Struggled with interview problems that could be solved in 15 minutes?
  • Wished you could study real-world problems?
If so, you need to read Elements of Programming Interviews.

mak(cse_DU)
Learning poster
Posts: 72
Joined: Tue May 30, 2006 5:57 pm
Location: bangladesh

Re: Correct outputs...

Post by mak(cse_DU) » Fri Dec 19, 2008 10:33 pm

jud wrote:
zxul767 wrote: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
Mak
Help me PLZ!!

tomtom85
New poster
Posts: 5
Joined: Tue Jun 01, 2010 7:48 am

Re: 10137 - The Trip

Post by tomtom85 » Tue Jun 08, 2010 12:48 am

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

Post Reply

Return to “Volume 101 (10100-10199)”

Who is online

Users browsing this forum: No registered users and 1 guest