10041 - Vito's Family

[trialsin]

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?

Thanks in advance

[trialsin]

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

[trialsin]

well, no thanks to the sample I/O, I've solved the problem. Use the median, not mean.

[stcheung]

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]

The average doesn't work for this problem, though another similar function might..

[r.z.]

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[500]={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[1]!=0)
{ j=rel[0]-rel[1];
if(j<0) j=-j;
rel[0]=j;
for(i=1;rel;i++)
{ rel=rel[i+1];
}
}
printf("%d\n",rel[0]);
}
}
}
[/c]

[shamim]

Well ur program does not consider the number of test cases,

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

[r.z.]

I think I misunderstood the problem

[r.z.]

[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[500];
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[0]),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]

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.]

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[500],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[0]),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]

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[1] = 3, rel5] = 1, rel[7] = 1, rel[9] = 1, rel[10] = 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]

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]

hey remember use only median


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

[bugzpodder]

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.