## 10137 - The Trip

All about problems in Volume 101. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

leocm
New poster
Posts: 22
Joined: Fri Jul 21, 2006 9:44 am
Location: Brasil
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
New poster
Posts: 14
Joined: Tue Jun 20, 2006 9:33 am

### 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 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
New poster
Posts: 14
Joined: Tue Jun 20, 2006 9:33 am

### goin crazy!

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
New poster
Posts: 1
Joined: Thu Feb 22, 2007 10:13 am
Location: Korea(Republic Of)/Gyunggido/Ilsan
Contact:

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

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);
}
}
``````
Hello

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea
..
Last edited by helloneo on Sat Dec 20, 2008 1:24 am, edited 1 time in total.

pgbrandao
New poster
Posts: 1
Joined: Sun Mar 18, 2007 5:29 am
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
New poster
Posts: 8
Joined: Sat Mar 10, 2007 10:20 am
for (int i = 0; i < numPpl; i++) {
cin >> temp;
avg += (int) (temp * 10000 + 1e-9) / numPpl;
cents = (int) (temp * 100 + 1e-9);
top = max(top, cents);

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

thx a lot........

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

### 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= (long)(x*100 +0.5);
sum += money;
}
mo=(float)sum/N;

sum1=sum2=0;
for(i=0;i<N;i++) {
if (money>mo)
sum1+=(long)(money - mo);
else
sum2+= (long)(mo-money);
}
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
Experienced poster
Posts: 158
Joined: Sun Feb 04, 2007 7:45 pm
Location: Medellin, Colombia

### Re: 10137 The Trip, please help!

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

egoruk
New poster
Posts: 1
Joined: Thu Jul 12, 2007 5:04 pm

### //Problems with the input\output

I'm a novice in the programming contests and i've got some stupid question about input\output. I've witen solutions for some problems but the result is always "wrong answer". I think it is because i've done incorrect input\output in my solutions. For example, for 10137 problem i've writen the next code:

#include <iostream>
#include <cmath>

using namespace std;

int main(int argc, char** argv)
{
int n;
int i;
float t = 0;
while(cin >> n)
{
if(n == 0)
break;
double sum_f = 0;
double* arr_f = new double[n];
for(i = 0; i < n; ++i)
{
cin >> arr_f;
}
double sr_f = 0.0f;
for(i = 0; i < n; ++i)
{
sr_f += arr_f * 1000.0;
sr_f = (int)sr_f;
}
sr_f /= n;
double* razn = new double[n];
for(i = 0; i < n; ++i)
razn = fabs(arr_f*1000.0 - sr_f);
for(i = 0; i < n; ++i)
if(arr_f*1000.0 > sr_f)
{
razn /= 10;
razn = (int)razn;
sum_f += razn;
}
sum_f /= 100.0;
cout << '\$' << sum_f << endl;
}

return 0;
}

Please, check my code and tell me about my errors.

P.s. Sorry for my English

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
In general, a submission is judged as 'Accepted' only if your program's output file is exactly the same as judge's output file.
That's why it's important to strictly follow problem's output format.

For 10137, output amount of money with exactly 2 digits after the decimal point.
printf("\$%.2f\n", sum_f); does that.

If you don't get accepted after fixing this, it'll be most probably because of rounding errors.
Don't panic, I'd suggest to solve a different problem. E.g. I think almost everyone starts with http://acm.uva.es/p/v1/100.html

iceAge
New poster
Posts: 1
Joined: Sat Jul 14, 2007 5:44 pm
Contact:

### 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=0;

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

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
New poster
Posts: 1
Joined: Thu Jul 19, 2007 5:06 am
Location: Guangdong, China
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
New poster
Posts: 34
Joined: Sat Nov 13, 2004 12:15 pm
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
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:
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

Please help me! Thanks
My code produces 0. Why the answer should be .01?
Ami ekhono shopno dekhi...
HomePage