10041 - Vito's Family
Moderator: Board moderators
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?
Thanks in advance
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
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]
[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]
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[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]
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]
[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?
#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?

he..he..he..
r.z. I think you misunderstand again. for this problem you must print the minimum total distance.
ex :
input :
output shouled be :
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
Code: Select all
23
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.....)
[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.....)
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[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
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
I'm not realy understand about your algo, but you can check with this IO :
output :
I think there is not tricky IO for this problem.
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
Code: Select all
7
8
163
99
-
- 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.