10137 - The Trip

[tomtom85]

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]

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]

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[1000],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]

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

[shuza]

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[1001], 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]

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

[thefourtheye]

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]

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]

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

[julienh]

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]

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.

Thanks in advance

[sohel]

A thread already exists for this topic: http://acm.uva.es/board/viewtopic.php?f=10&t=4055

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

[brianfry713]

Doesn't match the sample I/O.

[shimon0505004]

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]

Try solving it without using floating point.