10137 - The Trip
Moderator: Board moderators
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;
}
}
#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;
}
}
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.
// make it simple.. 
- 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.
- calculate the mean
Code: Select all
100
5.00 - 1st
...
5.00 - 98th
5.02 - 99th
4.97 - 100th
0
answer: $0.02

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]

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
-- E. W. Dijkstra
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]
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
-- E. W. Dijkstra
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;
}
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
[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

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......
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......
One possible solution is: The 3-cent guy gives 1 cent to any one of the others."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."
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org
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]
[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
-
- 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;
}
printf("$%.2Lf\n", ((below < above) ? below : above));
}
return 0;
}
[/c]
[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;
}
printf("$%.2Lf\n", ((below < above) ? below : above));
}
return 0;
}
[/c]
-
- New poster
- Posts: 28
- Joined: Mon Nov 15, 2004 5:00 pm
My Latest Code
My latest "corrected" code, still WA:
[c]#include <stdio.h>
int main(void)
{
int no, ii;
double total, above, below, right, student[1000];
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;
}
printf("$%.2lf\n", ((below < above) ? below : above));
}
return 0;
}
[/c]
[c]#include <stdio.h>
int main(void)
{
int no, ii;
double total, above, below, right, student[1000];
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;
}
printf("$%.2lf\n", ((below < above) ? below : above));
}
return 0;
}
[/c]
-
- Experienced poster
- Posts: 154
- Joined: Sat Apr 17, 2004 9:34 am
- Location: EEE, BUET
I don't really know what's the problem with this problem. I have long been in troubles with this one & tried in various ways all of which resulted in WA. But just now I've submitted the same problem in the programming-Challenge judge where it recieved AC. Can someone tell me what's wrong with this problem in UVa judge? 

You should never take more than you give in the circle of life.