10137 - The Trip

[leocm]

TY mf, but I've resolve this problem and i'm still get WA.
And I don't know why!!
Please, anyone can help me?

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;
}


[TripShock]

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 1000

float 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]

could someone please help me with this code...

Code: Select all

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

#define MAX 1000

float 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;
}


[infinite2802]

My program works O.K in example well.
but I got wrong answer.
what's wrong with this code??
please the right algorithm.
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);
   }
}


[helloneo]

..

[pgbrandao]

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!

[deadhunter411]

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

[aadelf]

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;
}

[andmej]

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.

[iceAge]

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 .

[YuanxunChen]

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


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

int
readcount ( 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.
Hoping for your reply[/code]

[paulmcvn]

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

Please help me! Thanks

[Jan]

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

Please help me! Thanks

My code produces 0. Why the answer should be .01?

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

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.

[Jan]

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