## 10137 - The Trip

Moderator: Board moderators

cyberjag
New poster
Posts: 1
Joined: Thu Mar 30, 2006 4:03 pm

### 10137

I dont know why I'm getting WA for this.

Code: Select all

import java.text.DecimalFormat;

/*
* The Trip
*/
class Main {

/**
* Read a string from the console. The string is terminated by a newline
*
* @return the input string (without the newline)
*/
String delim = "\n";
char c = delim.charAt(0);
StringBuffer s = new StringBuffer();
try {
while (delim.indexOf((int) c) == -1 && c != 65535) {
if (c != '\r') {
s.append((char) c);
}
}
} catch (Exception e) {
return (null);
}
if (s.toString().equals("")) {
return null;
}
return s.toString();
}

/*
*  Round the decimal to precision digits.
*/
double round(double x, int precision) {
return Math.floor(x * Math.pow(10.0, (double) precision) + 0.5)
/ Math.pow(10.0, (double) precision);
}

/*
* Calculate the min share.
*/
double calculate(double[] a) {
double avg = 0.0;
for (int i = 0; i < a.length; i++) {
avg += a[i];
}
avg = round(avg/a.length,2);
double a1 = 0, a2 = 0;
for (int i = 0; i < a.length; i++) {
if (a[i] > avg) {
a1 += a[i] - avg;
} else {
a2 += avg - a[i];
}
}
a1 = Math.min(a1, a2);
a1 = round(a1,2);
return a1;
}

void solve() {
int a;
double[] in;
while (true) {
a = Integer.parseInt(input);
if (a == 0) {
break;
}
in = new double[a];
for (int i = 0; i < a; i++) {
}
DecimalFormat df = new DecimalFormat();
df.applyPattern("0.00");
System.out.println(df.format(calculate(in)));
}
}

public static void main(String[] args) {
Main m = new Main();
m.solve();
}
}
Listing some input and output for this class.

input
3
10.00
20.00
30.00
4
15.00
15.01
3.00
3.01
5
5000.00
11.11
11.11
11.11
11.11
3
0.01
0.03
0.03
4
25.00
25.00
25.00
28.00
3
10.01
15.25
18.96
4
25.03
25.00
25.00
25.00
0

output
\$10.00
\$11.99
\$3991.11
\$0.01
\$2.25
\$4.73
\$0.02

John Herre
New poster
Posts: 6
Joined: Sat Jun 10, 2006 6:35 pm
Location: Bogota, Colombia
I worked the whole day on this problem!

Your suggestions helped me a lot, though I don't understand absolutely the reason the algorithm is the way it is... I was trying a different approach, but didn't work. I'll have to analyze it later, so I can really understand the idea behind the solution.

Well, I just wanted to share my code, I don't know completely 'iostream' object(s?) and their subtleties, so I decided to format the output for myself

Code: Select all

#include <iostream>
using namespace std;

int main()
{
int data[1000];
int n, i;
char inBuffer[9];
double average;

cin >> n;
while( n != 0 )
{
total = 0;
for( i = 0; i < n; i++)
{
cin >> inBuffer;
total += data[i];
}

average = (double)total / (double)n;
average = (long)(average + 0.5);

above = below = 0;
for( i = 0; i < n; i++ )
{
if( data[i] > average )
above += data[i] - (long)average;
else
below += (long)average - data[i];
}

answer = (above > below)? below : above;

cout << "\$" << answer/100 << ".";

cin >> n;
}
}

{
char input;
int i;
saveHere = 0;
i = 0;
while( (input = buffer[i]) != '\0' )
{
if( input != '.' )
saveHere = 10*saveHere + input - '0';
i++;
}
}

Oh, I didn't use an array of doubles to store data, just save integers, which are 100*<real data>... the last function performs the reading and ignoring dots.

JEHV

sklitzz
New poster
Posts: 32
Joined: Fri Dec 03, 2004 5:19 pm
Try searching through the forums, you'll find the answer to your question. I had a problem and found a solution without posting a new topic.

JoongHo
New poster
Posts: 2
Joined: Wed Jul 19, 2006 9:29 am

### 10137

#include <iostream>
#include <math.h>
using namespace std;

#define MAX 1000

class Node
{
public:
double money_exchange;

Node *next;
Node *prev;
};

int compare(const void *arg1, const void *arg2)
{
int p1, p2;
p1 = *(int*)arg1;
p2 = *(int*)arg2;
return (p2-p1);
}

int main()
{

Node * head = new Node;
Node * tail = new Node;
tail->next = tail;

int People;
int i;
int money_spent[1000];
int all_money_spent;
int each_money_spent;
int money_must_spent[1000];
int money_exchange;

while(cin>>People)
{
Node *p = new Node;

if (People == 0)
break;

for (i = 0; i<People; i++)
{
money_spent = 0;
}

all_money_spent = 0;
for (i = 0; i<People; i++)
{
double temp;
cin >> temp;
money_spent = (int)(temp*100 + 0.5);
all_money_spent += money_spent;
}

qsort((void*)money_spent, (size_t)(i), sizeof(int), compare);

each_money_spent = all_money_spent / People;
for (i = 0; i<People; i++)
money_must_spent = each_money_spent;

all_money_spent %= People;
for(i = 0; i<all_money_spent; i++)
money_must_spent++;

money_exchange = 0;
for (i = 0; i < People; i++)
{
money_exchange += abs(money_spent - money_must_spent);
}
money_exchange /= 2;

p->money_exchange = (double)(money_exchange / 100.0);

tail->prev->next = p;
p->prev = tail->prev;
tail->prev = p;
p->next = tail;
}

while(p!=tail)
{
cout.setf(ios::fixed, ios::floatfield);
cout.setf(ios::showpoint);
cout.precision(2);
cout << "\$" << p->money_exchange << endl;

p = p->next;
}
}

RalphLoizzo
New poster
Posts: 7
Joined: Mon Aug 28, 2006 7:02 pm

### I keep getting wrong answer no matter what I try on 10137

Can anyone help me with my source?

Code: Select all

#include <stdio.h>

int studentcount = 0;
int counter = 0;
int max = 0;
int min = 0;
unsigned long long int spent[1000];
unsigned long long int moneytomove, dollars, cents;
double temp = 0.00;
unsigned long long int diff;

int findmax(int studentcount)
{
int max=0;
for ( counter = 0; counter < studentcount; counter++)
{

if (spent[counter]>spent[max]) max=counter;
}

return max;
}
int findmin(int studentcount)
{

int min=0;
for (counter =0; counter < studentcount; counter++)
{

if (spent[counter]<spent[min]) min=counter;
}
return min;
}

int main (int argc, char *argv[])
{

scanf("%d", &studentcount);
while (studentcount != 0)
{
moneytomove=0;
for (counter = 0; counter < studentcount; counter++)
{
scanf("%Lf",&temp) ;
temp*=100.;
spent[counter]=temp;
}

/*	Find max and min, */
max=findmax(studentcount);
min=findmin(studentcount);
diff = spent[max]-spent[min];

while ( diff > 1 )
{
diff /= 2;

spent[max]-=diff;
spent[min]+=diff;
moneytomove += diff;
max=findmax(studentcount);
min=findmin(studentcount);
diff = spent[max]-spent[min];
}

dollars = moneytomove / 100;
cents = moneytomove % 100;

printf("\$%lld.",dollars);
if (cents < 10 ) printf("0");
printf("%lld\n",cents);

scanf("%d", &studentcount);
}
return 0;
}

User239
New poster
Posts: 3
Joined: Wed Sep 13, 2006 7:43 am

### 10137 I can't understand the example!!! Plz, Help!!!

Example is

Code: Select all

4
15.00
15.01
3.00
3.01
And we exchanged \$11.99.
But how money leave their hands? (For example fird gives x money to second or somewhat else?)

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
"15.00" gives \$5.99 to "3.01"; "15.01" gives \$6.00 to "3.00".
After these exchanges everyone has either \$9.00 or \$9.01, so everything is equalized within a cent.

User239
New poster
Posts: 3
Joined: Wed Sep 13, 2006 7:43 am
Oh, shit! I thought "within a cent" means equal amount of cents. For example \$9.005 and \$9.001. Now I know what is "within a cent"
P. S. I'm from Russia too.

zxul767
New poster
Posts: 11
Joined: Sat Nov 11, 2006 1:39 am

### I'm not sure, but there might be a problem with ...

... the way you're converting a double into an integer while reading the input. I had a similar problem in my first version coded in C (you're coding in C++, so I'm not sure if the same problem is present). For example, with the input:

Code: Select all

3
12.9
12.14
4.32
0
the value of 12.9 I obtained after multiplying it by 100 and storing the result into an integer was 1289 instead of 1290. For the rest of the numbers, everything was OK, but a single wrong conversion was enough to make the problem wrong here in UVA...

So I decided to read the input char by char and parse it so as to get a single integer representing the number of pennies. After that my problem got accepted on the first try (of course, I had already thought out the details about who should get the extra pennies).

zxul767
New poster
Posts: 11
Joined: Sat Nov 11, 2006 1:39 am

### Converting from double to integer might be a problem...

... I have seen several codes which do the same thing to parse the input for this problem. They read the money into a double, multiply it by 100 and then store the result into an integer. I think this may be a source of rounding errors, since I found that in one of my test cases 12.9 got converted to 1289 instead of 1290.

So I suggest you to avoid reading the input like that. I read the input parsing char by char so as to get the correct number of pennies (without worrying about rounding errors anymore) and that helped me get the code accepted.

By the way, I'm not sure whether this problem is actually a flaw in my compiler (gcc 4.0.3) or may be it's just a common thing to all of us using C/C++.

zxul767
New poster
Posts: 11
Joined: Sat Nov 11, 2006 1:39 am

### Correct outputs...

The correct outputs for the inputs:

Code: Select all

3
10.00
20.00
30.00
4
15.00
15.01
3.00
3.01
3
6.17
5.00
4.03
12
123.12
6.13
9.44
89.08
278.78
223.78
78.45
912.89
554.76
547.57
1781.89
907.07
2
4.99
15.00
1
10.00
15
0.01
0.01
0.01
0.01
0.01
0.01
0.01
0.01
0.01
0.01
0.01
0.01
0.01
0.01
0.03
5
5000.00
11.11
11.11
11.11
11.11
15
0.01
0.03
0.03
0.03
0.03
0.03
0.03
0.03
0.03
0.03
0.03
0.03
0.03
0.03
0.03
4
25.00
25.00
25.00
28.00
3
10.01
15.25
18.96
4
25.03
25.00
25.00
25.00
0
should be:

Code: Select all

\$10.00
\$11.99
\$1.10
\$2407.09
\$5.00
\$0.00
\$0.01
\$3991.11
\$0.01
\$2.25
\$4.73
\$0.02
Check it out, so you may find out what you're doing wrong.

zxul767
New poster
Posts: 11
Joined: Sat Nov 11, 2006 1:39 am

### If you're not sure what to do...

... you should read the problem over and over again until you understand it thoroughly. Any attempt to code a solution before understanding the problem is doomed to fail.

This, in fact, may also help you in making your code shorter, or cleaner, or maybe even both.

Good luck!

zxul767
New poster
Posts: 11
Joined: Sat Nov 11, 2006 1:39 am

### Hey, I've found some test data ...

... for which your problem fails to give out the correct answer:

Input:

Code: Select all

3
0,01
0,03
0.03
12
123.12
6.13
9.44
89.08
278.78
223.78
78.45
912.89
554.76
547.57
1781.89
907.07
15
0.01
0.03
0.03
0.03
0.03
0.03
0.03
0.03
0.03
0.03
0.03
0.03
0.03
0.03
0.03
Correct output:

Code: Select all

\$0.01
\$2407.09
\$0.01

Code: Select all

\$0.00
\$2407.08
\$0.00

leocm
New poster
Posts: 22
Joined: Fri Jul 21, 2006 9:44 am
Location: Brasil
I really don't understand this output.

My output gives:

Code: Select all

10.00
11.99
1.10
2407.10
5.00
0.00
0.01
3991.11
0.01
2.25
4.73
0.02
Only the 4th case is different, but I think that mine is correct!

My algorithm calculated that the amount beetween median and the lower prices is 2407.10 and the amount between the (median + 1) and the upper prices is 2407.08. How we have the give the greater, the answer is 2407.10.

Where I'm wrong?

Here is my code:

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;

for ( i = 0; i < estudantes; i++ )
{
scanf( "%lf", &valor );
aux = valor * 100;
vetor[i] = (int) aux;
total += valor;
}
mediaAux = total/estudantes;
media = (int) (100 * mediaAux);

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

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
You've rounding errors.
For instance, this part of your code rounds \$278.78 to 27877 cents (at least, on my computer):

Code: Select all

scanf( "%lf", &valor );
aux = valor * 100;
vetor[i] = (int) aux;
Oh, and don't forget to print "\$" in the output.