## 10137 - The Trip

Moderator: Board moderators

zubair
New poster
Posts: 17
Joined: Fri Apr 18, 2003 2:22 pm
i don't know what u have done? but u have to think who will get the extra cent if the total is not devisible evenly.
if the input is
4
15.05
15
3.01
3
or
4
15.02
15
3
3.01
zubair-CUET old sailor

problem
New poster
Posts: 27
Joined: Mon Nov 10, 2003 12:40 am

### 10137 wa plz help me

i dont understand how solve this problem.plz help me.

#include<stdio.h>

#include<math.h>
#include<string.h>
int a;
main()
{
int j;
static double po[1005],sum=0,sum1=0;
while(scanf("%d",&a)!=EOF)
{
if(a==0)
break;
for(j=0;j<a;j++)
{
scanf("%lf",&po[j]);
sum=sum+po[j];
}
sum=(floor(sum))/a;
for(j=0;j<a;j++)
{

if(po[j]>sum)
continue;

else
sum1=sum1+(sum-po[j]);
}
printf("$%.2lf\n",sum1); sum1=0;sum=0; } } lucky84 New poster Posts: 1 Joined: Tue Feb 10, 2004 5:05 pm ### 10137 the trip- a TIP hmm.. after some days of tries and failures finally my solution was accepted. So if anyone needs a tip here it is. • for holding data I use doubles my algorithm basicly looks like this: • calculate the mean round it down to the second place. i.e. 9.005 => 9.00 calculate amount of money above and below the rounded mean chose the greater amount. --i've coded it in c if someone needs some sample data here it is: Code: Select all 100 5.00 - 1st ... 5.00 - 98th 5.02 - 99th 4.97 - 100th 0 answer:$0.02
// make it simple..

Kentaro
New poster
Posts: 19
Joined: Thu Feb 05, 2004 4:41 am
I'm having trouble with this too.
Please look over my code if you have the time.

I think there is something wrong with the way I'm actually trying to solve the problem rather than the way in which I've coded it. My idea is to balance out the expenses in stages: take the largest number in the list and balance it with the smallest number in the list, using an extra penny if there is one to minimize the amount of money that exchanges hands at each step.

[cpp]
using namespace std;
#include <iostream>
#include <vector>
#include <cstdio>

bool balanced(vector<int>);
int findMin(vector<int>);
int findMax(vector<int>);

int main()
{
int num_students;
while (cin >> num_students)
{
// Are we done?
if (num_students == 0) break;

/* Create array of students; store all values in cents.
While we're at it, sum up the cent values. */
vector<int> students(num_students);
int sum = 0; // Even the most expensive trip can fit in an integer
for (int i = 0; i < num_students; i++)
{
double value;
cin >> value;
students = (int) (value * 100);
sum += students;
}

// How many cents should each student have?
int each = sum / num_students;

// How many extra pennies?
int extra = sum % num_students;

// How much money must be exchanged?
double shift = 0;

while (!balanced(students))
{
int min = findMin(students);
int max = findMax(students);

int amount = students[max] - each;
students[max] -= amount;
students[min] += amount;
shift += amount / 100.0;

/* If we have an extra penny, we can use it here to save us from
having to transfer a penny. */
if (extra != 0)
{
students[max]++;
students[min]--;
extra--;
shift -= 0.01;
}
}

printf("$%.2f\n", shift); } } bool balanced(vector<int> a) { int min = findMin(a); int max = findMax(a); if (a[max] - a[min] <= 1) return true; else return false; } int findMin(vector<int> a) { int minIndex = 0; int min = a[0]; for (int i = 1; i < a.size(); i++) { if (a < min) { minIndex = i; min = a; } } return minIndex; } int findMax(vector<int> a) { int maxIndex = 0; int max = a[0]; for (int i = 1; i < a.size(); i++) { if (a > max) { maxIndex = i; max = a; } } return maxIndex; } [/cpp] Computer Science is no more about computers than Astronomy is about telescopes. -- E. W. Dijkstra Kentaro New poster Posts: 19 Joined: Thu Feb 05, 2004 4:41 am Location: Canada, eh? Changed my approach to solving the problem to the suggestion of finding the mean rounded down to two decimal places, finding the amount spent above and below said mean and outputting the smaller amount. Still WA and now I'm convinced that there's some stupid round-off error lurking somewhere.... Please help.... [cpp] using namespace std; #include <iostream> #include <cstdio> int main() { int num_students; while (cin >> num_students) { if (num_students == 0) break; // The expenses list in cents and a sum of the expenses in cents. int students[num_students]; int sum = 0; for (int i = 0; i < num_students; i++) { double value; cin >> value; students = (int) (value * 100); sum += students; } // What is the average spent to the nearest cent? int average = sum / num_students; // How much was spent under the average? Over? int below = 0; int above = 0; for (int i = 0; i < num_students; i++) { if (students < average) below += average - students; else if (students > average) above += students - average; } double amount; if (below < above) amount = below / 100.0; else amount = above / 100.0; printf("$%.2f\n", amount);
}
}
[/cpp]
Computer Science is no more about computers than Astronomy is about telescopes.
-- E. W. Dijkstra

amstex
New poster
Posts: 5
Joined: Tue Jul 29, 2003 9:49 am
I also got WA but don't know why. Here is my code:

Code: Select all

#include <iostream>

int main() {
int pos, x, num, sum, result, avg, arr[1000], rem;
double temp;
cin>>num;

while (num!=0) {
pos = 0; sum = 0; result = 0;
for (x = 0; x<num; x++) {
cin>>temp; temp*=100;
arr[pos] = (int)temp;
sum += arr[pos];
++pos;
}
avg = sum/num;
rem = sum%num;
for (x = 0; x<num; x++) {
if (arr[x]>avg) {
if (rem>0) {
result += (arr[x]-avg-1);
--rem;
}
else result += (arr[x]-avg);
}
}

cout<<'$'<<result/100<<'.'<<result/10%10<<result%10<<endl; cin>>num; } return 0; } Subeen Experienced poster Posts: 127 Joined: Tue Nov 06, 2001 2:00 am Location: Bangladesh Contact: everbody who r getting WA on this problem please consider the thing who should get the extra pennies if the total does not divide evenly? Hope it will help... midra Experienced poster Posts: 119 Joined: Fri Feb 13, 2004 7:20 am Contact: ### 10137...WA I can't finish to understand 100% what I have to do.... so I make a this code: [c] #include <stdio.h> int main() { int i,temp,z=0; double n,res,res2,temp2,temp3; double s[1005],cant,cant2; empieza: res=res2=cant=z=cant2=0; scanf("%lf", &n); if (n==0) return 0; for (i=1; i<=n; i++) { scanf("%lf", &s); cant+=s; } cant=cant/n; /*cant es el promedio*/ cant2=cant/n; /*cant sin redondear*/ temp=cant*1000; temp2=(temp%10); temp2/=1000; /*if (temp2<0.005)*/ cant=cant-temp2; /*redondear para abajo*/ /* else cant=cant+(0.01-temp2); /*redondear para arriba*/ for (i=1; i<=n; i++) { if (s>cant) res+=s-cant; else if (s<cant) res2+=cant-s; } if (res<=0.009) { temp=res2*1000; temp2=(temp%10); temp2/=1000; res2=res2-temp2; printf("$%.2lf\n",res2);
}
else if (res2<=0.009)
{
temp=res*1000;
temp2=(temp%10);
temp2/=1000;
res=res-temp2;
printf("$%.2lf\n",res); } else if (res==res2) { temp=res*1000; temp2=(temp%10); temp2/=1000; res=res-temp2; printf("$%.2lf\n",res);
}
else if (res>res2)
{
temp=res*1000;
temp2=(temp%10);
temp2/=1000;
res=res-temp2;
printf("$%.2lf\n",res2); } else if (res<res2) { temp=res2*1000; temp2=(temp%10); temp2/=1000; res2=res2-temp2; printf("$%.2lf\n",res);
}

goto empieza;
}
[/c]

I have teste many Input/Output and it works OK but I still get WA.
If someone knows what is wrong with my program plz help me

Good luck!
bye

kiddi
New poster
Posts: 2
Joined: Thu Apr 22, 2004 6:53 pm

### Critical input...

can someone help me.....

I don't know what's wrong, I have the input :

1000
10000.00 (line 1)
10000.00 (line 2)
....
10000.00 (line 999)
9999.00 (line 1000)
2
10.00
10.00
3
10.00
20.00
30.00
4
15.00
15.01
3.00
3.01
100
5.00 (line 1)
5.00 (line 2)
...
5.00 (line 98 )
5.02 (line 99)
4.97 (line 97)
0

and the output :
$0.99$0.00
$10.00$11.99
$0.02 which should be right ??? but I still get WA.... I followed the method of calculating the mean, round it down, then calculate the amount of money above and below the rounded mean....... are there any critical inputs which I'm missing or...... kiha New poster Posts: 37 Joined: Sat Dec 20, 2003 10:59 pm Hi, I don't understand why for input 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 there is answer$0.01. Can anybody explain it to me? Any help appreciated. Greetings!
kiha

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."
One possible solution is: The 3-cent guy gives 1 cent to any one of the others.
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

samueljj
New poster
Posts: 18
Joined: Fri Jul 18, 2003 5:24 am
My code also getting WA.
[c]
#include <stdio.h>

int main(){
int n,i=0;
long double in,avg;
long students[1001],total=0,top,bottom;

#ifndef ONLINE_JUDGE
freopen("C:\\in.txt","r",stdin);
freopen("C:\\out.txt","w",stdout);
#endif

while(scanf("%d",&n)==1)
{
if(n==0)
break;
for(i=0;i<n;i++)
{
students=0;
scanf("%Lf",&in);
in=(long double)in*100+1e-9;
students=(int)(in);
total=total+students;
}
avg=(long double)total/n;
total=0;
top=0;
bottom=0;
for(i=0;i<n;i++)
{
if(students>avg)
top = top + (int)(students-avg);
else
bottom = bottom+(int)(avg-students);
}
if(top<bottom)
{
if(top>0)
printf("$%.2Lf\n",(long double)top/100); else printf("$%.2Lf\n",(long double)bottom/100);
}
else
{
if(bottom>0)
printf("$%.2f\n",(float)bottom/100); else printf("$%.2f\n",(float)top/100);
}

top=0;
bottom=0;
total=0;
}
return 0;
}

for the following test cases:
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
my programme's response:
$10.00$11.99
$1.09$2407.08
$5.00$0.00
$0.01$3991.08
$0.01$2.25
$4.73$0.02
which is not similiar some other's output for the same problem. I'm not sure which one is correct. If there is any critical input please mention. [/c]
novice programmer

SePulTribe
New poster
Posts: 28
Joined: Mon Nov 15, 2004 5:00 pm

### 10137 The Trip WA

Hi, I've been stuck on this problem for many days now even after searching through forums and modifying my code millions of time. I'm still very clueless as to what my error is. Please help. Here's my code at las modification. Thanks!
[c]#include <stdio.h>

int main(void)
{
int no, ii;
long double total, above, below, right, student[100];

while (1)
{
scanf("%d\n", &no);
if (!no)
break;
for (ii = 0, total = 0; ii < no; ii++)
{
scanf("%Lf\n", &student[ii]);
total += student[ii];
}
right = total / no * 100.0;
right = (int) right;
right /= 100.0;
above = below = 0;
for (ii = 0; ii < no; ii++)
{
if (student[ii] < right)
below += right - student[ii];
if (student[ii] > right)
above += student[ii] - right;
}

}
return 0;
}
[/c]