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

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

Re:

Post by tomtom85 » Tue Jun 08, 2010 9:01 am

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

Post by cathy » Tue Jun 22, 2010 6:17 pm

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

Post by md_yusuf » Fri Jun 25, 2010 11:24 pm

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
Experienced poster
Posts: 147
Joined: Mon Jun 07, 2010 11:43 am
Location: University Of Dhaka,Bangladesh
Contact:

Re: 10137 - The Trip

Post by Shafaet_du » Fri Oct 22, 2010 9:46 am

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

Post by shuza » Sat May 26, 2012 10:15 pm

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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10137 - The Trip

Post by brianfry713 » Fri Jun 01, 2012 2:29 am

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

Post by thefourtheye » Wed Feb 27, 2013 1:53 pm

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

Post by Ardeshir81 » Tue Jun 18, 2013 6:41 pm

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

Post by brianfry713 » Wed Jun 19, 2013 1:46 am

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

Post by julienh » Wed Jun 19, 2013 7:44 am

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

Post by shauryapoonia » Sun Jun 23, 2013 3:18 pm

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

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

Re: 10137- the trip problem

Post by sohel » Mon Jun 24, 2013 1:56 am

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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10137- the trip problem

Post by brianfry713 » Mon Jun 24, 2013 11:40 pm

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

Post by shimon0505004 » Mon Aug 05, 2013 11:39 am

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

Post by brianfry713 » Tue Aug 06, 2013 3:24 am

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

Post Reply

Return to “Volume 101 (10100-10199)”

Who is online

Users browsing this forum: No registered users and 1 guest