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

zubair
New poster
Posts: 17
Joined: Fri Apr 18, 2003 2:22 pm

Post by zubair »

i don't know what u have done? but u have to think who will get the extra cent if the total is not devisible evenly.
if the input is
4
15.05
15
3.01
3
or
4
15.02
15
3
3.01
what is the answer?
zubair-CUET old sailor

problem
New poster
Posts: 27
Joined: Mon Nov 10, 2003 12:40 am

10137 wa plz help me

Post by problem »

i dont understand how solve this problem.plz help me.


#include<stdio.h>

#include<math.h>
#include<string.h>
int a;
main()
{
int j;
static double po[1005],sum=0,sum1=0;
while(scanf("%d",&a)!=EOF)
{
if(a==0)
break;
for(j=0;j<a;j++)
{
scanf("%lf",&po[j]);
sum=sum+po[j];
}
sum=(floor(sum))/a;
for(j=0;j<a;j++)
{

if(po[j]>sum)
continue;

else
sum1=sum1+(sum-po[j]);
}
printf("$%.2lf\n",sum1);
sum1=0;sum=0;
}
}

lucky84
New poster
Posts: 1
Joined: Tue Feb 10, 2004 5:05 pm

10137 the trip- a TIP

Post by lucky84 »

hmm.. after some days of tries and failures finally my solution was accepted. So if anyone needs a tip here it is.
  • for holding data I use doubles
    my algorithm basicly looks like this:
    • calculate the mean
      round it down to the second place. i.e. 9.005 => 9.00
      calculate amount of money above and below the rounded mean
      chose the greater amount.
    --i've coded it in c
if someone needs some sample data here it is:

Code: Select all

100 
5.00 - 1st
...
5.00 - 98th
5.02 - 99th
4.97 - 100th
0
answer: $0.02
// make it simple.. :wink:

Kentaro
New poster
Posts: 19
Joined: Thu Feb 05, 2004 4:41 am
Location: Canada, eh?

Post by Kentaro »

I'm having trouble with this too. :(
Please look over my code if you have the time.

I think there is something wrong with the way I'm actually trying to solve the problem rather than the way in which I've coded it. My idea is to balance out the expenses in stages: take the largest number in the list and balance it with the smallest number in the list, using an extra penny if there is one to minimize the amount of money that exchanges hands at each step.

[cpp]
using namespace std;
#include <iostream>
#include <vector>
#include <cstdio>

bool balanced(vector<int>);
int findMin(vector<int>);
int findMax(vector<int>);

int main()
{
int num_students;
while (cin >> num_students)
{
// Are we done?
if (num_students == 0) break;

/* Create array of students; store all values in cents.
While we're at it, sum up the cent values. */
vector<int> students(num_students);
int sum = 0; // Even the most expensive trip can fit in an integer
for (int i = 0; i < num_students; i++)
{
double value;
cin >> value;
students = (int) (value * 100);
sum += students;
}

// How many cents should each student have?
int each = sum / num_students;

// How many extra pennies?
int extra = sum % num_students;

// How much money must be exchanged?
double shift = 0;

while (!balanced(students))
{
int min = findMin(students);
int max = findMax(students);

int amount = students[max] - each;
students[max] -= amount;
students[min] += amount;
shift += amount / 100.0;

/* If we have an extra penny, we can use it here to save us from
having to transfer a penny. */
if (extra != 0)
{
students[max]++;
students[min]--;
extra--;
shift -= 0.01;
}
}

printf("$%.2f\n", shift);
}
}

bool balanced(vector<int> a)
{
int min = findMin(a);
int max = findMax(a);
if (a[max] - a[min] <= 1) return true;
else return false;
}

int findMin(vector<int> a)
{
int minIndex = 0;
int min = a[0];
for (int i = 1; i < a.size(); i++)
{
if (a < min)
{
minIndex = i;
min = a;
}
}
return minIndex;
}

int findMax(vector<int> a)
{
int maxIndex = 0;
int max = a[0];
for (int i = 1; i < a.size(); i++)
{
if (a > max)
{
maxIndex = i;
max = a;
}
}
return maxIndex;
}
[/cpp]
Computer Science is no more about computers than Astronomy is about telescopes.
-- E. W. Dijkstra

Kentaro
New poster
Posts: 19
Joined: Thu Feb 05, 2004 4:41 am
Location: Canada, eh?

Post by Kentaro »

Changed my approach to solving the problem to the suggestion of finding the mean rounded down to two decimal places, finding the amount spent above and below said mean and outputting the smaller amount. Still WA and now I'm convinced that there's some stupid round-off error lurking somewhere....

Please help.... :cry:

[cpp]
using namespace std;
#include <iostream>
#include <cstdio>

int main()
{
int num_students;
while (cin >> num_students)
{
if (num_students == 0) break;

// The expenses list in cents and a sum of the expenses in cents.
int students[num_students];
int sum = 0;
for (int i = 0; i < num_students; i++)
{
double value;
cin >> value;
students = (int) (value * 100);
sum += students;
}

// What is the average spent to the nearest cent?
int average = sum / num_students;

// How much was spent under the average? Over?
int below = 0;
int above = 0;
for (int i = 0; i < num_students; i++)
{
if (students < average) below += average - students;
else if (students > average) above += students - average;
}

double amount;
if (below < above) amount = below / 100.0;
else amount = above / 100.0;

printf("$%.2f\n", amount);
}
}
[/cpp]
Computer Science is no more about computers than Astronomy is about telescopes.
-- E. W. Dijkstra

amstex
New poster
Posts: 5
Joined: Tue Jul 29, 2003 9:49 am

Post by amstex »

I also got WA but don't know why. Here is my code:

Code: Select all

#include <iostream>

int main() {
        int pos, x, num, sum, result, avg, arr[1000], rem;
        double temp;
        cin>>num;

        while (num!=0) {
                pos = 0; sum = 0; result = 0;
                for (x = 0; x<num; x++) {
                        cin>>temp; temp*=100;
                        arr[pos] = (int)temp;
                        sum += arr[pos];
                        ++pos;
                }
                avg = sum/num;
                rem = sum%num;
                for (x = 0; x<num; x++) {
                        if (arr[x]>avg) {
                                if (rem>0) {
                                        result += (arr[x]-avg-1);
                                        --rem;
                                }
                                else result += (arr[x]-avg);
                        }
                }

                cout<<'$'<<result/100<<'.'<<result/10%10<<result%10<<endl;
                cin>>num;
        }
        return 0;
}

Subeen
Experienced poster
Posts: 127
Joined: Tue Nov 06, 2001 2:00 am
Location: Bangladesh
Contact:

Post by Subeen »

everbody who r getting WA on this problem please consider the thing
who should get the extra pennies if the total does not divide evenly?
Hope it will help... :wink:

midra
Experienced poster
Posts: 119
Joined: Fri Feb 13, 2004 7:20 am
Contact:

10137...WA

Post by midra »

I can't finish to understand 100% what I have to do.... so I make a this code:

[c]
#include <stdio.h>

int main()
{
int i,temp,z=0;
double n,res,res2,temp2,temp3;
double s[1005],cant,cant2;
empieza:
res=res2=cant=z=cant2=0;
scanf("%lf", &n);
if (n==0)
return 0;
for (i=1; i<=n; i++)
{
scanf("%lf", &s);
cant+=s;
}
cant=cant/n; /*cant es el promedio*/
cant2=cant/n; /*cant sin redondear*/
temp=cant*1000;
temp2=(temp%10);
temp2/=1000;
/*if (temp2<0.005)*/
cant=cant-temp2; /*redondear para abajo*/
/* else
cant=cant+(0.01-temp2); /*redondear para arriba*/

for (i=1; i<=n; i++)
{
if (s>cant)
res+=s-cant;
else if (s<cant)
res2+=cant-s;
}

if (res<=0.009)
{
temp=res2*1000;
temp2=(temp%10);
temp2/=1000;
res2=res2-temp2;
printf("$%.2lf\n",res2);
}
else if (res2<=0.009)
{
temp=res*1000;
temp2=(temp%10);
temp2/=1000;
res=res-temp2;
printf("$%.2lf\n",res);
}
else if (res==res2)
{
temp=res*1000;
temp2=(temp%10);
temp2/=1000;
res=res-temp2;
printf("$%.2lf\n",res);
}
else if (res>res2)
{
temp=res*1000;
temp2=(temp%10);
temp2/=1000;
res=res-temp2;
printf("$%.2lf\n",res2);
}
else if (res<res2)
{
temp=res2*1000;
temp2=(temp%10);
temp2/=1000;
res2=res2-temp2;
printf("$%.2lf\n",res);
}

goto empieza;
}
[/c]

I have teste many Input/Output and it works OK but I still get WA.
If someone knows what is wrong with my program plz help me

Good luck!
bye :D

kiddi
New poster
Posts: 2
Joined: Thu Apr 22, 2004 6:53 pm

Critical input...

Post by kiddi »

can someone help me.....

I don't know what's wrong, I have the input :

1000
10000.00 (line 1)
10000.00 (line 2)
....
10000.00 (line 999)
9999.00 (line 1000)
2
10.00
10.00
3
10.00
20.00
30.00
4
15.00
15.01
3.00
3.01
100
5.00 (line 1)
5.00 (line 2)
...
5.00 (line 98 )
5.02 (line 99)
4.97 (line 97)
0

and the output :
$0.99
$0.00
$10.00
$11.99
$0.02

which should be right ??? but I still get WA....

I followed the method of calculating the mean, round it down, then calculate the amount of money above and below the rounded mean.......

are there any critical inputs which I'm missing or......

kiha
New poster
Posts: 37
Joined: Sat Dec 20, 2003 10:59 pm

Post by kiha »

Hi,

I don't understand why for input
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
there is answer $0.01. Can anybody explain it to me? Any help appreciated. Greetings!
kiha

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Post by 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."
One possible solution is: The 3-cent guy gives 1 cent to any one of the others.
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

samueljj
New poster
Posts: 18
Joined: Fri Jul 18, 2003 5:24 am

Post by samueljj »

My code also getting WA.
[c]
#include <stdio.h>

int main(){
int n,i=0;
long double in,avg;
long students[1001],total=0,top,bottom;

#ifndef ONLINE_JUDGE
freopen("C:\\in.txt","r",stdin);
freopen("C:\\out.txt","w",stdout);
#endif


while(scanf("%d",&n)==1)
{
if(n==0)
break;
for(i=0;i<n;i++)
{
students=0;
scanf("%Lf",&in);
in=(long double)in*100+1e-9;
students=(int)(in);
total=total+students;
}
avg=(long double)total/n;
total=0;
top=0;
bottom=0;
for(i=0;i<n;i++)
{
if(students>avg)
top = top + (int)(students-avg);
else
bottom = bottom+(int)(avg-students);
}
if(top<bottom)
{
if(top>0)
printf("$%.2Lf\n",(long double)top/100);
else
printf("$%.2Lf\n",(long double)bottom/100);
}
else
{
if(bottom>0)
printf("$%.2f\n",(float)bottom/100);
else
printf("$%.2f\n",(float)top/100);
}

top=0;
bottom=0;
total=0;
}
return 0;
}

for the following test cases:
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
my programme's response:
$10.00
$11.99
$1.09
$2407.08
$5.00
$0.00
$0.01
$3991.08
$0.01
$2.25
$4.73
$0.02
which is not similiar some other's output for the same problem. I'm not sure which one is correct. If there is any critical input please mention. [/c]
novice programmer

SePulTribe
New poster
Posts: 28
Joined: Mon Nov 15, 2004 5:00 pm

10137 The Trip WA

Post by SePulTribe »

Hi, I've been stuck on this problem for many days now even after searching through forums and modifying my code millions of time. I'm still very clueless as to what my error is. Please help. Here's my code at las modification. Thanks!
[c]#include <stdio.h>

int main(void)
{
int no, ii;
long double total, above, below, right, student[100];

while (1)
{
scanf("%d\n", &no);
if (!no)
break;
for (ii = 0, total = 0; ii < no; ii++)
{
scanf("%Lf\n", &student[ii]);
total += student[ii];
}
right = total / no * 100.0;
right = (int) right;
right /= 100.0;
above = below = 0;
for (ii = 0; ii < no; ii++)
{
if (student[ii] < right)
below += right - student[ii];
if (student[ii] > right)
above += student[ii] - right;
}

printf("$%.2Lf\n", ((below < above) ? below : above));
}
return 0;
}
[/c]

SePulTribe
New poster
Posts: 28
Joined: Mon Nov 15, 2004 5:00 pm

My Latest Code

Post by SePulTribe »

My latest "corrected" code, still WA:

[c]#include <stdio.h>

int main(void)
{
int no, ii;
double total, above, below, right, student[1000];

while (1)
{
scanf("%d\n", &no);
if (!no)
break;
for (ii = 0, total = 0; ii < no; ii++)
{
scanf("%lf\n", &student[ii]);
total += student[ii];
}
right = total / no * 100.0;
right = (int) right;
right /= 100.0;
above = below = 0;
for (ii = 0; ii < no; ii++)
{
if (student[ii] < right)
below += right - student[ii];
if (student[ii] > right)
above += student[ii] - right;
}

printf("$%.2lf\n", ((below < above) ? below : above));
}
return 0;
}
[/c]

Mohammad Mahmudur Rahman
Experienced poster
Posts: 154
Joined: Sat Apr 17, 2004 9:34 am
Location: EEE, BUET

Post by Mohammad Mahmudur Rahman »

I don't really know what's the problem with this problem. I have long been in troubles with this one & tried in various ways all of which resulted in WA. But just now I've submitted the same problem in the programming-Challenge judge where it recieved AC. Can someone tell me what's wrong with this problem in UVa judge? :o
You should never take more than you give in the circle of life.

Post Reply

Return to “Volume 101 (10100-10199)”