## 10041 - Vito's Family

Moderator: Board moderators

trialsin
New poster
Posts: 3
Joined: Thu Oct 17, 2002 10:03 am
Location: Simon Fraser University

### 10041 - Vito's Family

This problem seems quite trivial, but my solution still receives WA.
My algorithm simply calculates the mean of the housenumbers and checks
the minimum distance for each of the two integers around the mean. Is this
completely wrong, or is there some tricky input to this problem?

trialsin
New poster
Posts: 3
Joined: Thu Oct 17, 2002 10:03 am
Location: Simon Fraser University

### 10041

Apparently I'm partially dyslexic. The problem number is
actually 10041, not 10014. Hopefully that helps to get some replies.

trialsin
New poster
Posts: 3
Joined: Thu Oct 17, 2002 10:03 am
Location: Simon Fraser University
well, no thanks to the sample I/O, I've solved the problem. Use the median, not mean.

stcheung
Experienced poster
Posts: 114
Joined: Mon Nov 18, 2002 6:48 am
Contact:

### 10041 WA

A relatively easy problem I think. My approach is to first find the average of all the streets where the houses were located at. Then given the average, either round it appropriately to get the street number of Vito's house. Finally, just add up all the distances from Vito's house to his relatives' houses. But I keep getting WA...anything I missed?

[cpp]

#include <iostream.h>
#include <stdlib.h>
#include <math.h>

int main()
{
int numcases, numrelatives, street;
cin >> numcases;
long double average;
for(int i=0; i<numcases; i++)
{
cin >> numrelatives;
int houses[numrelatives];
average = 0;
for(int j=0; j<numrelatives; j++)
{
cin >> houses[j];
average = (average * j + houses[j])/(j+1);
}
street = ((int)(average - 0.5) < (int)average) ?
(int)average : (int)average + 1;
// cout << "street: " << street << "\n";
unsigned result = 0;
for(int k=0; k<numrelatives; k++)
{
result += abs(houses[k] - street);
}

cout << result << "\n";
}

return 0;
}[/cpp]

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:
The average doesn't work for this problem, though another similar function might.. r.z.
Learning poster
Posts: 56
Joined: Thu Jun 05, 2003 1:57 pm

### 10041

Again I don't know why what's wrong with my code.....
or maybe I understand the problem wrongly?

[c]
#include<stdio.h>

void main()
{ int rel={0},i,j,n,N,k;

while(scanf("%d",&N)!=EOF)
{
for(k=0;k<N;k++)
{ scanf("%d",&n);
for(i=0;rel;i++)
rel=0;
for(i=0;i<n;i++)
scanf("%d",&rel);
while(rel!=0)
{ j=rel-rel;
if(j<0) j=-j;
rel=j;
for(i=1;rel;i++)
{ rel=rel[i+1];
}
}
printf("%d\n",rel);
}
}
}
[/c]

shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA
Well ur program does not consider the number of test cases,

besides i can tell u that this code will get TLE.

r.z.
Learning poster
Posts: 56
Joined: Thu Jun 05, 2003 1:57 pm
I think I misunderstood the problem r.z.
Learning poster
Posts: 56
Joined: Thu Jun 05, 2003 1:57 pm
[c]
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

int sort_function( const void *a, const void *b);

void main()
{ int i,j,N,r,rel;
while(scanf("%d",&N)!=EOF)
{ for(j=0;j<N;j++)
{ scanf("%d",&r);
for(i=0;i<r;i++)
scanf("%d",&rel);
qsort(rel,r,sizeof(rel),sort_function);
if(r%2==0) printf("%d\n",rel[(r/2)-1]);
else printf("%d\n",rel[r/2]);
}
}

}

int sort_function( const void *a, const void *b)
{
return( strcmp((char *)a,(char *)b) );
}
[/c]

I've modified my code
I search the median to seek the minimum cost
is my algortihm right?

why I keep getting WA? Hisoka
Experienced poster
Posts: 120
Joined: Wed Mar 05, 2003 10:40 am
Location: Indonesia
he..he..he..

r.z. I think you misunderstand again. for this problem you must print the minimum total distance.

ex :
input :

Code: Select all

``````1
7
5 1 7 1 9 1 10``````
output shouled be :

Code: Select all

``23``

r.z.
Learning poster
Posts: 56
Joined: Thu Jun 05, 2003 1:57 pm
ok recode it

[c]
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

int sort_function( const void *a, const void *b);

void main()
{ int i,j,N,r,rel,t,opt,hasil;
while(scanf("%d",&N)!=EOF)
{ for(j=0;j<N;j++)
{ opt=0;
scanf("%d",&r);
for(i=0;i<r;i++)
scanf("%d",&rel);
qsort(rel,r,sizeof(rel),sort_function);
t=r/2;
for(i=0;i<r;i++)
{ hasil=rel-rel[t];
if(hasil<0) hasil=-hasil;
opt+=hasil;
}
printf("%d\n",opt);
}
}

}

int sort_function( const void *a, const void *b)
{
return( strcmp((char *)a,(char *)b) );
}
[/c]

but still WA.....

damn.......Am I making a mistake in reading the problem again? (If I am....damn me.....)

rodriwan
New poster
Posts: 8
Joined: Mon Jun 03, 2002 8:13 pm

### input/output cases

Hi Hisoka, my program is is OK with the sample input that you've putted here, can you send me some more i/o cases so I can test my program? I keep getting wa.

My algorithm work as follows: first I set a vector with the street numbers and get the total sum of these numbers, in the case of your input, the vector would look like this:

rel = 3, rel5] = 1, rel = 1, rel = 1, rel = 1
and the sum would be: 5 + 1 + 7 + 1 + 9 + 1 + 10 = 34

Vito's House number would be 34/nrelatives, 4.xxxx, since this number must be exact I calc the min dist for 4 and for 5, and take the minimum of the two.

the min_dist routine just get the pos of vitors house and do get the sum of all distances.

thx, Rodrigo

Hisoka
Experienced poster
Posts: 120
Joined: Wed Mar 05, 2003 10:40 am
Location: Indonesia
I'm not realy understand about your algo, but you can check with this IO :

Code: Select all

``````4
3
1 1 8
4
3 1 5 7
10
30 25 15 1 1 1 23 23 90 10
5
1 1 1 1 100``````
output :

Code: Select all

``````7
8
163
99``````
I think there is not tricky IO for this problem.

miras
Learning poster
Posts: 98
Joined: Sat Jun 14, 2003 1:45 pm

### 2202

hey remember use only median

MEDIAN f.e if we have 1 2 4 then median is 2

bugzpodder
Experienced poster
Posts: 147
Joined: Fri Jun 13, 2003 10:46 pm

### 10041 - Vito's Family

I am trying to prove mathematically that the median is the correct answer for this question but i am not getting anywhere. could someone give me a mathematical proof? Thanks in advance.
Last edited by bugzpodder on Mon Aug 23, 2004 8:18 pm, edited 2 times in total.