## 10137 - The Trip

Moderator: Board moderators

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong
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
Contact:
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
Yep, I've just got AC although my program outputs \$0.00 for the above case!

So what is the correct algorithm?

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

### 10137 - The Trip

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;

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
New poster
Posts: 18
Joined: Mon Dec 17, 2007 11:35 pm
Location: Queretaro
Contact:

### Wa

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

New poster
Posts: 32
Joined: Tue Feb 13, 2007 1:31 pm

### coincidence or not?!

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    */
/*****************************/

#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=elist=0.0;
elist=elist=0.0;
for(int i=0; i<n; ++i)
{
if(e.at(i)<ts_exps)
elist+=((e.at(i)-ts_exps)*-1);
else if(e.at(i)>ts_exps)
elist+=(e.at(i)-ts_exps);
if(e.at(i)<s_exps)
elist+=((e.at(i)-s_exps)*-1);
else if(e.at(i)>s_exps)
elist+=(e.at(i)-s_exps);
}
cout<<elist<<" "<<elist<<" "<<elist<<" "<<elist<<endl;
quicksort(elist,0,3);
cout<<elist;
}
cout<<endl;
}

return 0;
}
``````

jud
New poster
Posts: 4
Joined: Mon Jan 28, 2008 7:24 pm

### Re: Correct outputs...

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

New poster
Posts: 32
Joined: Tue Feb 13, 2007 1:31 pm

### Re: Correct outputs...

thx for ur test cases

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

Code: Select all

``````cout<<elist<<" "<<elist<<" "<<elist<<" "<<elist<<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
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

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

### Re: 10137 - The Trip

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

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

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. 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

### Re: Correct outputs...

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

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