10137 - The Trip

[Junayeed]

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

Thanks

[stcheung]

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]

[jpfarias]

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:

Code: Select all

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

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

Thanks!

JP!

[PJYelton]

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.

[PJYelton]

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]

[xidao]

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.

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

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):

Code: Select all

3
10.01
15.25
18.96
0

Then I realized that the data 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;
}

So that's the scoop. I'm desperate. I've been knocking my head against this problem for 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.

[xidao]

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

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

Code: Select all

4
25.00
25.00
25.00
28.00
0

[ggll]

Basically, given the total cost and the 'within one cent' rule, you know what the final cost distribution should be. To minimize the exchange, try to choose the cost closer to the actual cost. However, this is not always possible, so choose high if start high, choose low if start low....

[ggll]

I think {1, 3, 3} will break your program. Looks like you put negative amount in the pile sometimes. Other than that it looks fine.

[PJYelton]

Actually {1,3,3} doesn't break it, it returns $1.33 as expected.

As for putting negative numbers in, I changed the > signs to >= signs so now it is impossible to put in negative numbers, and still get a wrong answer.

[ggll]

Actually I mean {0.01, 0.03, 0.03}, i.e. a case in which round = true and all element above average = total + 1.

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]

[PJYelton]

Oops, yeah, I caught that mistake a couple of days ago and forgot to mention it. However, I still get a wrong answer. Also, it doesn't state whether or not you are supposed to print the zero in front of the decimal point if the answer is less than a dollar. I've tried it both ways and also got wrong answers on both. Here is my latest 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()
{
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]

[ggll]

The algorithm itself is fine. I just got AC with it. The problem must be in the I/O part. I am not quite familiar with c++ so I am not sure here. You do need to put a '0' there for less than 1 dollar. Try long long data type.

[PJYelton]

Woot! It finally worked! The fact that you said the algorithm worked in your language got me to scrap using ints all together and only worked with doubles, using a setprecision function at the end and some nasty conversions to check to makes sure half pennies weren't used. But it worked! Thank god, I can finally stop thinking about this stupid program!

Thanks!!

[ggll]

Good to know that it finally works for you.

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]