## 10137 - The Trip

**Moderator:** Board moderators

### 10137 - Need help

I think it is a easy problem, but i am getting WA. Please help me with some tricky input and output

Thanks

Thanks

### problem confusing

I was not surprised when I got WA for the question. I didn't think I really understand what they want. What I basically did is to find the difference between the 2 amounts in the middle. For instance, if the amounts were

2 3 5 8 10 20, the middle 2 amounts are 5 & 8 and so I will output 3.

If the amounts were 2 3 5 8 10, I would check whether (5 - 3) is smaller or (8 - 5) is and then output the smaller difference (in this case 5 - 3 = 2).

[cpp]#include <iostream.h>

#include <stdlib.h>

#include <string>

#include <vector>

#include <algorithm>

int main()

{

int numstudents, size, half;

double input, output;

while(true)

{

cin >> numstudents;

vector<double> amounts;

if(numstudents <= 0)

break;

for(int i=0; i<numstudents; i++)

{

cin >> input;

amounts.push_back(input);

}

sort(amounts.begin(), amounts.end());

size = amounts.size();

half = size/2;

if(size%2 == 1)

{

if((amounts[half] - amounts[half - 1]) <

(amounts[half+1] - amounts[half]))

output = amounts[half] - amounts[half-1];

else output = amounts[half+1] - amounts[half];

}

else output = amounts[half] - amounts[half - 1];

cout << "$" << output;

if((int)output == output)

cout << ".00";

cout << "\n";

}

return 0;

}[/cpp]

2 3 5 8 10 20, the middle 2 amounts are 5 & 8 and so I will output 3.

If the amounts were 2 3 5 8 10, I would check whether (5 - 3) is smaller or (8 - 5) is and then output the smaller difference (in this case 5 - 3 = 2).

[cpp]#include <iostream.h>

#include <stdlib.h>

#include <string>

#include <vector>

#include <algorithm>

int main()

{

int numstudents, size, half;

double input, output;

while(true)

{

cin >> numstudents;

vector<double> amounts;

if(numstudents <= 0)

break;

for(int i=0; i<numstudents; i++)

{

cin >> input;

amounts.push_back(input);

}

sort(amounts.begin(), amounts.end());

size = amounts.size();

half = size/2;

if(size%2 == 1)

{

if((amounts[half] - amounts[half - 1]) <

(amounts[half+1] - amounts[half]))

output = amounts[half] - amounts[half-1];

else output = amounts[half+1] - amounts[half];

}

else output = amounts[half] - amounts[half - 1];

cout << "$" << output;

if((int)output == output)

cout << ".00";

cout << "\n";

}

return 0;

}[/cpp]

### 10137 - The Trip

I think this is not a hard problem, but there may be any tricks...

My approach is calculate the sum of the distances to the average of values < average.

Something like this:

But I got WA! Can anyone explain me what I need to do in this problem?

Thanks!

JP!

My approach is calculate the sum of the distances to the average of values < average.

Something like this:

Code: Select all

```
if (value[i] < average) {
totall += average - value[i];
}
```

Thanks!

JP!

### You forgot something...

You are forgetting that sometimes the people who overpay need to give back more money than what the people who pay less need to receive. Like for example:

4 people, one pays $25.03, the other all pay $25. The average is $25.0075. Now all the people who pay less are within one cent, so your algorithm would return zero, but the person who paid more NEEDS to pay 2 cents or else he won't be within one cent, so the answer should be 2 cents.

4 people, one pays $25.03, the other all pay $25. The average is $25.0075. Now all the people who pay less are within one cent, so your algorithm would return zero, but the person who paid more NEEDS to pay 2 cents or else he won't be within one cent, so the answer should be 2 cents.

### 10137 The Trip, please help!

I agree with everyone that this shouldn't be a hard question, but for some reason I keep getting a wrong answer.

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. But I get the wrong answer even though every thing I have tried has given me a correct answer!

Could someone please give me a hint as to what I am missing or a set of data that would break my idea please? Here is my code:

[cpp]

/* @JUDGE_ID: 32250TW 10137 C++ "Simple Iteration" */

/* @BEGIN_OF_SOURCE_CODE */

#include<iostream>

#include<string>

#include<vector>

using namespace std;

int max(int x, int y) {if (x>y) return x; else return y;}

int min(int x, int y) {if (x<y) return x; else return y;}

int main()

{

while (1)

{

int num, x, total=0, most=0, least=0;

bool round=false;

vector<int> vecF;

cin>>num;

if (!num)

break;

for (x=0; x<num; x++)

{

double d;

cin>>d;

vecF.push_back(int(d*100));

total+=(vecF[x]);

}

if (total%num!=0)

round=true;

total/=num;

for (x=0; x<vecF.size(); x++)

{

if (round && vecF[x]>total+1)

most+=(vecF[x]-(total+1));

else if (!round && vecF[x]>total)

most+=(vecF[x]-total);

else

least+=(total-vecF[x]);

}

//cout<<least<<" "<<most<<endl;

least=max(least,most);

cout<<"$"<<least/100<<".";

if (least%100==0)

cout<<"00"<<endl;

else if (least%100<10)

cout<<"0"<<least%100<<endl;

else

cout<<least%100<<endl;

}

return 0;

}

/* @END_OF_SOURCE_CODE */

[/cpp]

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. But I get the wrong answer even though every thing I have tried has given me a correct answer!

Could someone please give me a hint as to what I am missing or a set of data that would break my idea please? Here is my code:

[cpp]

/* @JUDGE_ID: 32250TW 10137 C++ "Simple Iteration" */

/* @BEGIN_OF_SOURCE_CODE */

#include<iostream>

#include<string>

#include<vector>

using namespace std;

int max(int x, int y) {if (x>y) return x; else return y;}

int min(int x, int y) {if (x<y) return x; else return y;}

int main()

{

while (1)

{

int num, x, total=0, most=0, least=0;

bool round=false;

vector<int> vecF;

cin>>num;

if (!num)

break;

for (x=0; x<num; x++)

{

double d;

cin>>d;

vecF.push_back(int(d*100));

total+=(vecF[x]);

}

if (total%num!=0)

round=true;

total/=num;

for (x=0; x<vecF.size(); x++)

{

if (round && vecF[x]>total+1)

most+=(vecF[x]-(total+1));

else if (!round && vecF[x]>total)

most+=(vecF[x]-total);

else

least+=(total-vecF[x]);

}

//cout<<least<<" "<<most<<endl;

least=max(least,most);

cout<<"$"<<least/100<<".";

if (least%100==0)

cout<<"00"<<endl;

else if (least%100<10)

cout<<"0"<<least%100<<endl;

else

cout<<least%100<<endl;

}

return 0;

}

/* @END_OF_SOURCE_CODE */

[/cpp]

### 10137 -- The (AWFUL) Trip

Re: 10137, The Trip ...

This is an ugly problem. I'm not sure exactly what I'm missing, but I see that the problem has been solved successfully by a number of others, so this isn't impossible, it's just, well, hard. There's two possibilities: 1) there's some special case of data that I just haven't counted on AT ALL, or 2) i don't understand what the problem is asking for. Sigh.

That said, here's my approach so far. I've mainly tried two possibilities at a solution, the first being the computational approach that everyone seems to attempt: Subtract the underpayers from the average paid, keep track of the extra pennies, make sure the overpayers keep those.

Well, I generate solid results with all sample data I can think of with my computational algorithm. Also, originally I was assuming that the data would be supplied in the following form (this single input here only as an example, my code takes multiple inputs into account):

Then I realized that the data

Results? Squat. No help whatsoever.

My second approach is written as a simulation, and it generates seemingly identical results to my computational approach, with one exception, that it times out instead of generating a wrong answer.

Okay, so this is easy to understand--since my simulation loop terminates only on iterations that happen as a result of conditions, I must not be understanding all the conditions, and so not accounting for them. Right now, the simulation just sorts the list of values, then iterates starting from the highest and the lowest, taking a penny from the highest, giving it to the lowest. Once one of those values has reached a target value, which depends on the disposition of "extra pennies", the next value is chosen, up or down the list as appropriate.

So that's the scoop. I'm desperate. I've been knocking my head against this problem for

This is an ugly problem. I'm not sure exactly what I'm missing, but I see that the problem has been solved successfully by a number of others, so this isn't impossible, it's just, well, hard. There's two possibilities: 1) there's some special case of data that I just haven't counted on AT ALL, or 2) i don't understand what the problem is asking for. Sigh.

That said, here's my approach so far. I've mainly tried two possibilities at a solution, the first being the computational approach that everyone seems to attempt: Subtract the underpayers from the average paid, keep track of the extra pennies, make sure the overpayers keep those.

Code: Select all

```
#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <numeric>
#include <string>
#include <strstream>
using namespace std;
int main()
{
int A, amounts[1000], d, e, i, h, j, k, n, p, R, S, T;
string a, b, ch;
strstream ss;
cin >> n;
while (n) {
for (i=0; i<n; ++i) {
d=0;
p=0;
cin >> a;
S=a.size();
for (j=0; j<S; ++j) {
if (d) ++p;
if (a[j]!='.') b+=a[j];
else ++d;
}
ss << b;
ss >> h;
for (k=0; k<2-p; ++k)
h*=10;
amounts[i]=h;
ss.clear();
b.erase();
}
T=accumulate(amounts, amounts+n, 0)/n;
sort(amounts, amounts+n);
A=0;
R=0;
e=0;
for (i=0; i<n; ++i)
if (amounts[i]<T)
R+=(T-amounts[i]);
if (accumulate(amounts, amounts+n, 0)%n) {
for (i=0; i<n; ++i)
if (amounts[i]>T) {
A+=(amounts[i]-T);
++e;
}
R+=(A-R)-e;
}
ch=R%100<10?".0":".";
cout << "$" << R/100 << ch << R%100 << endl;
cin >> n;
}
return 0;
}
```

Code: Select all

```
3
10.01
15.25
18.96
0
```

*might*not come in a convenient, ready-pak, #0.00# form, so I adjusted the code to read in the values and account for only dollars, or for dollars and single decimal digits.Results? Squat. No help whatsoever.

My second approach is written as a simulation, and it generates seemingly identical results to my computational approach, with one exception, that it times out instead of generating a wrong answer.

Okay, so this is easy to understand--since my simulation loop terminates only on iterations that happen as a result of conditions, I must not be understanding all the conditions, and so not accounting for them. Right now, the simulation just sorts the list of values, then iterates starting from the highest and the lowest, taking a penny from the highest, giving it to the lowest. Once one of those values has reached a target value, which depends on the disposition of "extra pennies", the next value is chosen, up or down the list as appropriate.

Code: Select all

```
#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <numeric>
#include <string>
#include <strstream>
using namespace std;
int main()
{
int A, amounts[1000], d, e, i, h, j, k, n, p, R, S, T;
string a, b, ch;
strstream ss;
cin >> n;
while (n) {
for (i=0; i<n; ++i) {
d=0;
p=0;
cin >> a;
S=a.size();
for (j=0; j<S; ++j) {
if (d) ++p;
if (a[j]!='.') b+=a[j];
else ++d;
}
ss << b;
ss >> h;
for (k=0; k<2-p; ++k)
h*=10;
amounts[i]=h;
ss.clear();
b.erase();
}
T=accumulate(amounts, amounts+n, 0)/n;
e=accumulate(amounts, amounts+n, 0);
e=e%n;
sort(amounts, amounts+n);
R=0;
i=0;
j=n-1;
while (i<j) {
if (e && amounts[j]-amounts[i]<=1) break;
if (!e && amounts[j]==amounts[i]) break;
++amounts[i];
--amounts[j];
++R;
if (e) {
if(amounts[i]==T+1) ++i;
if(amounts[j]==T+1) { --j; --e; }
} else {
if(amounts[i]==T) ++i;
if(amounts[j]==T) --j;
}
}
ch=R%100<10?".0":".";
cout << "$" << R/100 << ch << R%100 << endl;
cin >> n;
}
return 0;
}
```

**WAY**too long, and I'm frustrated beyond belief. Every hour more I give to this problem robs me of a little bit of my sanity. I'm losing it. I've almost lost it completely. So if anyone can give any insights, suggestions, extreme sample data (I've tried a number of extreme possibilities, like 1000 students with wacko values, 1 student paying $10,000.00, 999 paying nothing, etc.), hints, clues, examples, a bonk on the head, whatever, I'd appreciate it. Because I don't understand why I can't get this. And it's killing me. Slowly. I'm dying. Help.### This is goofy.

The "median difference" thing is goofy. I can't belive that algorithm succeeded.

It can't, for instance, handle this input:

It can't, for instance, handle this input:

Code: Select all

```
4
25.00
25.00
25.00
28.00
0
```

If your current version looks like this, it should be fine. I tried this(not exactly the same) and passed. Please post the new version if there are still problems.

[cpp]

for (x=0; x<vecF.size(); x++)

{

if (round && vecF[x]>=total+1) // add '=' here

most+=(vecF[x]-(total+1));

else if (!round && vecF[x]>total)

most+=(vecF[x]-total);

else

least+=(total-vecF[x]);

}[/cpp]

[cpp]

/* @JUDGE_ID: 32250TW 10137 C++ "Simple Iteration" */

/* @BEGIN_OF_SOURCE_CODE */

#include<iostream>

#include<string>

#include<vector>

using namespace std;

int max(int x, int y) {if (x>y) return x; else return y;}

int min(int x, int y) {if (x<y) return x; else return y;}

int main()

{

vector<int> vecF; // vector holding each amount paid

while (1)

{

int num; // number of students

int x;

int total=0; // total amount spent in pennies

int more=0; // amount over the average spent in pennies

int less=0; // amount under the average spent in pennies

bool round=false; // average came out evenly or not

vecF.clear();

cin>>num;

if (!num)

break;

for (x=0; x<num; x++)

{

double d;

cin>>d;

d*=100;

vecF.push_back(int(d));

total+=(vecF[x]);

}

if (total%num!=0)

round=true;

total/=num;

for (x=0; x<vecF.size(); x++)

{

if (round && vecF[x]>=total+1)

more+=(vecF[x]-(total+1));

else if (!round && vecF[x]>total)

more+=(vecF[x]-total);

else

less+=(total-vecF[x]);

}

less=max(less,more);

cout<<"$"<<less/100<<".";

if (less%100<10)

cout<<"0";

cout<<less%100<<endl;

}

return 0;

}

/* @END_OF_SOURCE_CODE */ [/cpp]

Thanks!!

Actually I was doing it the other way around. I used int everywhere. It is always safer to work with integers.

Now you mentioned it, I managed to get your original version passed with one modification(and the '=' of course).

[cpp] for (x=0; x<num; x++)

{

double d;

cin>>d;

vecF.push_back(int(d*100 + 1e-10)); // add EPS here

total+=(vecF[x]);

}[/cpp]