## 10137 - The Trip

Moderator: Board moderators

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

### Re:

deadhunter411 wrote:for (int i = 0; i < numPpl; i++) {
cin >> temp;
avg += (int) (temp * 10000 + 1e-9) / numPpl;
cents = (int) (temp * 100 + 1e-9);
top = max(top, cents);

Can someone explain " + 1e-9 " ???

thx a lot........

Probably this is a little late, the 1e-9 is an epsilon, sometimes when you have a float number that should be "2" it gets a "1.999999999", if you aplly a floor to that number it will return a 1. the epsilon is there to complete the number and get a "2" as it should be.

cathy
New poster
Posts: 2
Joined: Sat Mar 28, 2009 11:47 pm

### Re: 10137 - The Trip

Can someone please explain why the answer to this case is \$0.02 and not \$0.01? Seems like you only need to move one penny from the second person to the first person and then they are all within one penny of each other.

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
Thanks, Cathy

md_yusuf
New poster
Posts: 9
Joined: Fri Jun 25, 2010 11:09 pm

### Re: 10137 - The Trip

im gatting WA im sick of this problem...... here is my code.... i thought i was a easy probem.... plz help me
#include<iostream>
using namespace std;
double make2(double d)
{
long int a,e;
double b,c,f,g;
a=d;
b=d-a;
c=b*100;
e=c;
g=double(e*.01);
c=b*1000;
e=c;
if((e%1000)>4)
f=a+g+.01;
else
f=a+g;
return f;
}
int main()
{
double a,average,dif,sum1,sum2;
long int i,n;
freopen("in.txt","r",stdin);
while(scanf("%d",&n)&&n)
{
for(i=0;i<n;i++)
scanf("%lf",&a);
average=0;
for(i=0;i<n;i++)
average=average+a;
average=average/n;
average=make2(average);
sum1=0;
sum2=0;
for(i=0;i<n;i++)
{
if(a>average)
{
dif=a-average;
sum2=sum2+dif;
}
else
{
dif=average-a;
sum1=sum1+dif;
}
}
if(sum1<sum2)
printf("\$%.2lf\n",sum1);
else
printf("\$%.2lf\n",sum2);
}
return 0;
}
it solve all the case that i have found in website......
plz help me..... Shafaet_du
Experienced poster
Posts: 147
Joined: Mon Jun 07, 2010 11:43 am
Contact:

### Re: 10137 - The Trip

I used long long and long double everywhere and got accepted in one chance.

shuza
New poster
Posts: 4
Joined: Fri May 04, 2012 1:59 am

### Re: 10137 - The Trip

i have tried above input and answer is right....but still getting WA......i don't understand why?????

Code: Select all

``````#include <stdio.h>
#include <stdlib.h>

int main()
{
int i, n ;
double a, avg, ans, more, less ;
while( scanf( "%d", &n )==1 )
{
if( n==0 )
break ;
avg=0 ;
for( i=0 ; i<n ; i++ )
{
scanf( "%lf", &a[i] ) ;
avg+=(double) a[i]/n ;
}
ans=0 ;
less=0 ;
more=0 ;
for( i=0 ; i<n ; i++ )
if( a[i]<avg )
more+=avg-a[i] ;
else
less+=a[i]-avg ;
if( less>more )
ans=more ;
else
ans=less ;
ans*=100 ;
n=ans ;
ans=(double) n/100 ;
printf( "\$%.2lf\n", ans ) ;
}
return 0;
}
``````

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 10137 - The Trip

Input:

Code: Select all

``````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
0``````
AC Output:
\$2407.09
Check input and AC output for thousands of problems on uDebug!

thefourtheye
New poster
Posts: 5
Joined: Sat Jun 04, 2011 9:36 am

### Re: You forgot something...

PJYelton wrote:You are forgetting that sometimes the people who overpay need to give back more money than what the people who pay less need to receive. Like for example:

4 people, one pays \$25.03, the other all pay \$25. The average is \$25.0075. Now all the people who pay less are within one cent, so your algorithm would return zero, but the person who paid more NEEDS to pay 2 cents or else he won't be within one cent, so the answer should be 2 cents.
Thanks... My mind sees only what is obvious to it... Ardeshir81
New poster
Posts: 8
Joined: Wed Jun 12, 2013 5:51 pm

### Re: 10137 - The Trip

HI Everyone!
I've been stucked in this problem for a while, the answer of the second input example always was 12.00 (instead of 11.99)
Today I finally could do something that the answer becomes 11.99 .
But I couldn't understand the algorithm correctly.
I tried to figure it out but I always reached 12.00

Please take a look and check where of my calculations is incorrect :
(Sorry if my English is terrible)

There are 4 persons.
Person 1 -> Spent 15.01
Person 2 -> Spent 15.00
Person 3 -> Spent 3.01
Person 4 -> Spent 3.00

What we should do is to calculate the average of all costs and then exchange money between these people so that everyone's costs reach the average.
The average is : 15.01 + 15.00 + 3.01 + 3.00 = 36.02
36.02 / 4 = 9.005

Now,
for Person 1 -> 15.01 - 9.005 = 6.005 It means that this person should GIVE 6.005 dollars to reach the average
for Person 2 -> 15.00 - 9.005 = 5.995 It means that this person should GIVE 5.995 dollars to reach the average
for Person 3 -> 9.005 - 3.01 = 5.995 It means that this person should TAKE 5.995 dollars to reach the average
for Person 4 -> 9.005 - 3.00 = 6.005 It means that this person should TAKE 6.005 dollars to reach the average

So the simplest thing ( the minimum money exchange) is that person 1 GIVE 6.005 to person 4 (who should TAKE 6.005)
and person 2 GIVE 5.995 to person 3 (who should TAKE 5.995)

So the minimum money exchange is : 5.995 + 6.005 = 12.00

I think I'm wrong in last part, I mean is there any other better way so this 4 people can exchange money?
Thank you ALL!

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 10137 - The Trip

After the trip, each student's expenses are tallied and money is exchanged so that the net cost to each is the same, to within one cent. In the past, this money exchange has been tedious and time consuming. 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.

Don't consider half cents. If person 1 gives person 4 \$6, and person 2 gives person 3 \$5.99, then they'll end up equalized within a cent.
1: \$15.01 - \$6.00 = \$9.01
2: \$15.00 - \$5.99 = \$9.01
3: \$3.01 + \$5.99 = \$9.00
4: \$3.00 + \$6.00 = \$9.00
Check input and AC output for thousands of problems on uDebug!

julienh
New poster
Posts: 1
Joined: Wed Jun 19, 2013 6:16 am

### Re: 10137 - The Trip

Hi everyone !
These might get usefull for I/O :
(Please check that it is correct, but I got AC using these)

Code: Select all

``````long int read_amount(){
long int amount = 0;
string money;
cin >> money;

for (int iCar = 0; iCar < money.size(); ++iCar) {
char& caracter = money[iCar];
if (isdigit(caracter)) {
amount *= 10;
amount += (caracter - '0');
}
}
return amount;
}
``````
and :

Code: Select all

``````cout << "\$" << std::setprecision(2)  << fixed << YOUR_ANSWER << "\n";
``````

shauryapoonia
New poster
Posts: 1
Joined: Sun Jun 23, 2013 3:12 pm

### 10137- the trip problem

hi,
i have written code for this problem as

#include<iostream>
#define SIZE 1001
using namespace std;
int main()
{
double expenses[SIZE];
int num;
cin>>num;
while(num!=0)
{ double input=0;double sum=0.0f;
for(int i=0;i<num;i++)
{
cin>>input;
expenses=input;
sum += expenses; //total sum of expenditure in order to calculate mean
}
double mean=(sum)/num; //mean calculated here
double transfer=0.0f;

for(int i=0;i<num;i++)
{
if(expenses<mean) //all those expenses less then mean are substracted in order to calculate total transfer
transfer += mean-expenses;
}
cout<<'\$'<<transfer<<endl;

cin>>num;
}
return 0;
}

but i am getting wring answer for this one.

If anyone can suggest me any reading material and correction possible in this code so that it runs properly.

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

### Re: 10137- the trip problem

Search the board first before posting. If one exists, make your post in that one.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 10137- the trip problem

Doesn't match the sample I/O.
Check input and AC output for thousands of problems on uDebug!

shimon0505004
New poster
Posts: 1
Joined: Wed Jul 31, 2013 1:48 pm

### Re: 10137 - The Trip

Hi all,
Can anyone help me ? why does my code show WA?

Code: Select all

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

int main(void)
{
int nNumberOfStudent;
while(1)
{
cin>>nNumberOfStudent;
if(nNumberOfStudent==0)
{
break;
}
double *nStudent = new double[nNumberOfStudent];
double nSum=0;
for(int nCounter=0;nCounter<nNumberOfStudent;nCounter++)
{
cin >> nStudent[nCounter];
nSum += nStudent[nCounter];
}
double highx=(int)((nSum/nNumberOfStudent + 0.0099)*100);
double lowx=(int)((nSum/nNumberOfStudent)*100);
highx /= 100;
lowx /= 100;

double cost=0;
for(int nCounter=0;nCounter<nNumberOfStudent;nCounter++)
{
if(nStudent[nCounter]>highx)
{
cost += (nStudent[nCounter]-highx);
}
else if(nStudent[nCounter]<lowx)
{
cost += (lowx-nStudent[nCounter]);
}
}
cost /=2;
cout << "\$" << setiosflags(ios::fixed)<<setprecision(2) <<cost <<endl;
}
return 0;
}

``````

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 10137 - The Trip

Try solving it without using floating point.
Check input and AC output for thousands of problems on uDebug!