10137 - The Trip

[zubair]

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
what is the answer?

[problem]

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]

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]

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]

[Kentaro]

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]

[amstex]

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]

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]

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]

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]

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!

[Observer]

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

[samueljj]

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]

[SePulTribe]

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]

[SePulTribe]

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]

[Mohammad Mahmudur Rahman]

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?