## 10137 - The Trip

Moderator: Board moderators

TY mf, but I've resolve this problem and i'm still get WA.
And I don't know why!!

Code: Select all
`#include <stdio.h>#define MAX(A, B) ( (A) > (B) ? (A) : (B) )int main(){    int i, estudantes, media, troca, trocaMenor, trocaMaior, vetor[1005];    double total, valor, aux, mediaAux;    while ( scanf( "%d", &estudantes ) == 1 && estudantes )    {           total = 0.0;               for ( i = 0; i < estudantes; i++ )        {            scanf( "%lf", &valor );            total += valor;            aux = 1000 * valor;             vetor[i] = (int) (aux/10);        }                mediaAux = total/estudantes;        media = 1000 * mediaAux;        media = (int) (media/10);        trocaMenor = trocaMaior = 0;        for ( i = 0; i < estudantes; i++ )        {            if ( vetor[i] < media )                trocaMenor += media - vetor[i];            else                if ( vetor[i] > media + 1)                    trocaMaior += vetor[i] - media - 1;        }        troca = MAX(trocaMenor, trocaMaior);        valor = (double) troca / 100.0;            printf("\$%.2lf\n", valor);           }    return 0;}`
leocm
New poster

Posts: 22
Joined: Fri Jul 21, 2006 9:44 am
Location: Brasil

### V101 - 10137 - WA

Why is this code WA? It works for all the sample input on this board.

Code: Select all
`#include <stdio.h>#include <stdlib.h>#define MAX 1000float round(float a){    char b[128] = { 0 };        sprintf(b, "%.2f", a);    a = atof(b);        return a;}int main(){    int Students = 0;    float Spent[MAX] = { 0.0 };    float Total = 0.0;    float TotalNew = 0.0;    float Exchange = 0.0;    int ExtraCents = 0;    int GuysWhoPaidMore = 0;        int i = 0;        while (1)    {        scanf("%d", &Students);        if (!Students)            break;                    Total = 0.0;        Exchange = 0.0;                for (i = 0; i < Students; i++)        {            scanf("%f", &Spent[i]);            Total += Spent[i];        }                Total /= Students;        Total *= 100;        TotalNew = (float)((int)Total);        Total /= 100;        TotalNew /= 100;        GuysWhoPaidMore = 0;                for (i = 0; i < Students; i++)        {            if (Spent[i] > TotalNew)            {                Exchange += round(Spent[i] - TotalNew);                GuysWhoPaidMore++;            }        }        Total -= TotalNew;        Total *= Students;        Total = round(Total);        Total += 0.005;        Total *= 100;        ExtraCents = (int)(Total);        if (GuysWhoPaidMore < ExtraCents)            Exchange -= (float)GuysWhoPaidMore / 100;        else            Exchange -= (float)ExtraCents / 100;                printf("\$%.2f\n", Exchange);    }        return 0;}`

TripShock
New poster

Posts: 14
Joined: Tue Jun 20, 2006 9:33 am

### goin crazy!

Code: Select all
`#include <stdio.h>#include <stdlib.h>#define MAX 1000float round(float a){    char b[128] = { 0 };        sprintf(b, "%.2f", a);    a = atof(b);        return a;}int main(){    int Students = 0;    float Spent[MAX] = { 0.0 };    float Total = 0.0;    float TotalNew = 0.0;    float Exchange = 0.0;    int ExtraCents = 0;    int GuysWhoPaidMore = 0;        int i = 0;        while (1)    {        scanf("%d", &Students);        if (!Students)            break;                    Total = 0.0;        Exchange = 0.0;                for (i = 0; i < Students; i++)        {            scanf("%f", &Spent[i]);            Total += Spent[i];        }                Total /= Students;        Total *= 100;        TotalNew = (float)((int)Total);        Total /= 100;        TotalNew /= 100;        GuysWhoPaidMore = 0;                for (i = 0; i < Students; i++)        {            if (Spent[i] > TotalNew)            {                Exchange += round(Spent[i] - TotalNew);                GuysWhoPaidMore++;            }        }        Total -= TotalNew;        Total *= Students;        Total = round(Total);        Total += 0.005;        Total *= 100;        ExtraCents = (int)(Total);        if (GuysWhoPaidMore < ExtraCents)            Exchange -= (float)GuysWhoPaidMore / 100;        else            Exchange -= (float)ExtraCents / 100;                printf("\$%.2f\n", Exchange);    }        return 0;}`

TripShock
New poster

Posts: 14
Joined: Tue Jun 20, 2006 9:33 am

### 10137 The Trip........WA plz....

My program works O.K in example well.
what's wrong with this code??
Plz~

Code: Select all
`#include<iostream>#include<stdio.h>using namespace std;void main(){   while(1)   {      int i;      float average=0;      float sum=0;            float don[1005];      int n;      cin >> n;      if(n == 0)         break;      for(i=0;i<n;i++)      {         cin >> don[i];         sum += don[i];      }      average = sum / n;      float cha1=0, cha2=0;      for(i=0;i<n;i++)      {         if(don[i] > average)            cha2 += (don[i]-average);         else            cha1 += (average-don[i]);      }      float cha3; // cha3 = min(cha1, cha2)      if(cha1 < cha2)         cha3 = cha1;      else         cha3 = cha2;      printf("\$%.2f\n",cha3 - 0.005);   }}`
Hello
infinite2802
New poster

Posts: 1
Joined: Thu Feb 22, 2007 10:13 am
Location: Korea(Republic Of)/Gyunggido/Ilsan

..
Last edited by helloneo on Sat Dec 20, 2008 1:24 am, edited 1 time in total.
helloneo
Guru

Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

Hello all!

Sorry to resurface this buried thread, however I've been stuck for a while on this problem. (Also, I'm still a newbie, so bear with me. )

It took me a while to get the grasp of the leftover cents concept (and of course get it working), but that no longer seems to be my problem. As a matter of fact, from all the (allegedly correct) test cases I've seen, all of them work! Yet my the judge doesn't accept it claiming WA.

Here's the code:

Code: Select all
`#include <iostream>#include <cstring>#include <iomanip>#include <cmath>using namespace std;int iabs (int i) {   if (i < 0) {      return -1 * i;   } else {      return i;   }}int main () {   int n, i, j, sum, min, max, changehands;   double average;   do {      cin >> n;      if (n != 0 && !cin.eof()) {         int *array;         array = new int [n];         sum = 0;         for (i = 0; i < n; i++) {            double value;            cin >> value;            array [i] = (int) floor (value * 100 + 0.5);            sum += array[i];         }                  average = (double) sum / n;         min = (int) floor (average);         max = (int) ceil (average);         changehands = 0;         for (i = 0; i < n; i++) {            int crediti;            if (array[i] >= max) {               crediti = array[i] - max;            } else {               crediti = array[i] - min;            }            for (j = 0; j < n; j++) {               int creditj;               if (array[j] >= max) {                  creditj = array[j] - max;               } else {                  creditj = array[j] - min;               }               if (((crediti < 0) && (creditj > 0)) ||                  ((crediti > 0) && (creditj < 0))) {                  if (iabs (creditj) > iabs (crediti)) {                     changehands += iabs(crediti);                     creditj += crediti;                     array[j] += crediti;                     array[i] -= crediti;                     crediti = 0;                  } else {                     changehands += iabs(creditj);                     crediti += creditj;                     array[i] += creditj;                     array[j] -= creditj;                      creditj = 0;                  }               }            }            if ((crediti != 0) && (array[i] != min) && (array[i] != max)) {               for (j = 0; j < n; j++) {                  if ((array[j] == max) && (array[i] < min)) {                     array[j]--;                     array[i]++;                     changehands++;                  } else if ((array[j] == min) && (array[i] > max)) {                     array[j]++;                     array[i]--;                     changehands++;                  }               }            }         }         cout << "\$" << setprecision (2) << setiosflags(ios::fixed|ios::showpoint) << (float) changehands / 100 << "\n";         delete[] array;      }   } while (n != 0 && !cin.eof());}`

Again, I've tested many examples against my code, including some by hand, and it appears to be correct! Please tell me it's just some extra whitespace or something silly like that, I just don't see where I went wrong.

Thanks!
pgbrandao
New poster

Posts: 1
Joined: Sun Mar 18, 2007 5:29 am

for (int i = 0; i < numPpl; i++) {
cin >> temp;
avg += (int) (temp * 10000 + 1e-9) / numPpl;
cents[i] = (int) (temp * 100 + 1e-9);
top = max(top, cents[i]);

Can someone explain " + 1e-9 " ???

thx a lot........
New poster

Posts: 8
Joined: Sat Mar 10, 2007 10:20 am

### Help

could anyone help? I tested my code with all the testsets in this board, and all came out right. However I get a Wrong anwser result.

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int main(int argc,char *argv[])
{
float x,mo,result;
long i,N,money[1000],sum,sum1,sum2;

scanf("%d",&N);

while (N!=0) {
sum=0;
for(i=0;i<N;i++){
scanf("%f",&x);
money[i]= (long)(x*100 +0.5);
sum += money[i];
}
mo=(float)sum/N;

sum1=sum2=0;
for(i=0;i<N;i++) {
if (money[i]>mo)
sum1+=(long)(money[i] - mo);
else
sum2+= (long)(mo-money[i]);
}
sum = sum1>sum2?sum1:sum2;
result = (float)(sum)/100;
if ((result*100)<sum)
result+=0.001;

printf("\$%.2f\n",result);
scanf("%d",&N);
}

return 0;
}
New poster

Posts: 5
Joined: Fri May 18, 2007 7:30 pm

PJYelton wrote:Basically this is my algorithm. First find out what the average amount is, rounded down. Then I cycle through all of the amounts, and if the amount is less than the average, I add the difference to the LESS pile, and if the amount is more than the average, then I add the difference to the MORE pile. If I had to round down when I first calculated the difference, then I add one to the average when I do the difference between a pile that is greater and the average.

Now I figure that the greater of the two amounts is the minimum amount of money that needs to be transferred. Like for example if the LESS pile is \$2.00 and the MORE pile is \$2.01, then the minimum amount of money transfered is \$2.01 since if only 2 dollars were transferred, then the MORE people wouldn't be within one cent. So I always return the greater of the two numbers.

In the part that is bold, you add one dollar or one cent? I can't understand the algorithm.
Runtime errors in Pascal are reported as Wrong Answers by the online judge. Be careful.

Are you dreaming right now?
http://www.dreamviews.com

andmej
Experienced poster

Posts: 158
Joined: Sun Feb 04, 2007 7:45 pm
Location: Medellin, Colombia

### trip 10137

any body who can find any test case with wrong output for this code it will be appreciative plz?
#include<iostream>
#include<cmath>
using namespace std;

void main()
{
long student;
double cost[1000];
double total;
double net,lowernet,uppernet;
int average;
int netint;
int jam;
cin>>student;

while(student != 0)
{

total=0;
lowernet=0;
uppernet=0;
net=0;

for(int i=0 ; i<1000 ; i++)
cost[i]=0;

for(int i=0 ; i<student ; i++)
{
cin>>cost[i];
}
for(int i=0 ; i<student ; i++)
{
total=total + cost[i];
}

jam=int((total/student)*100);

if ((jam%2)==0)
average=int(ceil((total/student)*100));
else
average=int(floor((total/student)*100));

for(int k=0 ; k<student ; k++)
{
if((cost[k]*100)>average)
uppernet=uppernet+((cost[k]*100)-average);
else
lowernet=lowernet+ (average - (cost[k]*100));
}

if(lowernet<uppernet)
net=lowernet;
else
net=uppernet;

netint=int(net);

if((netint%100)<10)
cout<<'\$'<<(netint/100)<<".0"<<(netint%100)<<endl;
else
cout<<'\$'<<(netint/100)<<'.'<<(netint%100)<<endl;

cin>>student;
}
}

this code cover all test cases that was suggested in other posts .
iceAge
New poster

Posts: 1
Joined: Sat Jul 14, 2007 5:44 pm

Hello, world and everyone!

This is my first time to post in the forum in English, and my English is not so
good but i hope you can bear it and i'll try my best.

for iceAge:
Input :
Code: Select all
` 5 0.17 0.00 0.00 0.00 0.000`

Output :
Code: Select all
` 13 `
;

Though this prob looks easy, but it really puzzled me much and I've already wasted two days solving this prob.

I've seen others' codes on this board but it seems hard for me to understand. Below is my own algorithm:

First calculate the average account ( ave = (int )total / n, note that the ave is the floor of the true ave ) . then divide the students into two parts:
the high students, whose account is bigger than ave and low student , whose account is lower or equal to ave.
it's said that the difference account can be 1 cent , so the legal account is ave and ave+1;
Then i found that we can exchange money between the two major part
and ignore the detail on single person. (obvious, low student needn't give out money). So the prob is simple now. Only two aspects:
low student get money from the high to increase their account to at least ave;
high student get money from the low to reduce to ave+1 of ave;

The nest step is easy , since both of the require should be meeted, just print the bigger.

It is a fun thing. I originally write the material above because my prog always WA. But just after I post my code, and submit it again, I found it AC! I want to delete it all now but it really spend me some time to write the thing above so i remain it there.

Now I found out the main problem is that my origin prog cound't read the
input properly, i think int is enough to hold the account but that is the main thing cause my prog wrong.
Code: Select all
`intreadcount ( int n){   int i;   int total=0;   double count;   for ( i=0; i< n; i++){      scanf ("%lf\n", &count);      stdt[i] = count * 100;      total += count * 100;   }   return total;}`

I just change all the int into double including everyone's account and it is accepted.
I'm new in C and I puzzled about the way C read number and the calculation. Somtimes it read a 1.000 to 1.001(float) and sometimes 12/5=2.399999999999? Can anyone who has the experience tell me why and provide a way to handle the input. The single account is small and i think using double to handle it is a waste.
YuanxunChen
New poster

Posts: 1
Joined: Thu Jul 19, 2007 5:06 am
Location: Guangdong, China

I got WA many times for this problem and quite dont understand why

After that, I found this on alogrithmist.com:
"
Calculate the average expenditure and round it to two decimal places. (You'll need to write your own rounding function). Now the expenditure can be equalized in two ways. First, by adding the amount spent minus the average amount (for spent amount > average). Then the sum rounded to two decimal places is the answer.
"

I dont understand that solution. For example:
15
0.01
0.01
0.01
....
0.03

Then the rounded average is 0.01. So by that solution, the answer is min(0, 0.03) = 0
??
The correct answer should be 0.01

paulmcvn
New poster

Posts: 34
Joined: Sat Nov 13, 2004 12:15 pm

paulmcvn wrote:I dont understand that solution. For example:
15
0.01
0.01
0.01
....
0.03

Then the rounded average is 0.01. So by that solution, the answer is min(0, 0.03) = 0
??
The correct answer should be 0.01

My code produces 0. Why the answer should be .01?
Ami ekhono shopno dekhi...
HomePage
Jan
Guru

Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm

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.

Clearly, 0.01 != 0.03, within a cent or not. If your AC code prints 0.00, then I think the judge input is too weak.
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org
Observer
Guru

Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

You are right. The judge data is weak indeed. But then what is your procedure.

I found the average, round it, and a = sum(greateritem-avg), b=(avg-smallerItem).

Then printed min(a,b) with rounding..

May be I have to go through the problem again....
Ami ekhono shopno dekhi...
HomePage
Jan
Guru

Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm