10041 - Vito's Family

All about problems in Volume 100. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

10041 - Vito's Family

Post by trialsin » Thu Oct 17, 2002 10:18 am

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
New poster
Posts: 3
Joined: Thu Oct 17, 2002 10:03 am
Location: Simon Fraser University

10041

Post by trialsin » Thu Oct 17, 2002 7:32 pm

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

Post by trialsin » Thu Oct 17, 2002 10:54 pm

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

Post by stcheung » Mon Nov 25, 2002 9:33 am

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:

Post by Larry » Tue Nov 26, 2002 12:49 am

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

Post by r.z. » Sun Jun 15, 2003 10:45 am

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]

User avatar
shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA

Post by shamim » Tue Jun 17, 2003 11:24 am

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

Post by r.z. » Tue Jun 17, 2003 1:42 pm

I think I misunderstood the problem

:)

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

Post by r.z. » Wed Jun 18, 2003 2:28 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[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? :cry:

Hisoka
Experienced poster
Posts: 120
Joined: Wed Mar 05, 2003 10:40 am
Location: Indonesia

Post by Hisoka » Wed Jun 18, 2003 3:06 pm

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

Post by r.z. » Wed Jun 18, 2003 6:21 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[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
New poster
Posts: 8
Joined: Mon Jun 03, 2002 8:13 pm

input/output cases

Post by rodriwan » Thu Jun 19, 2003 9:33 pm

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
Experienced poster
Posts: 120
Joined: Wed Mar 05, 2003 10:40 am
Location: Indonesia

Post by Hisoka » Fri Jun 20, 2003 1:53 pm

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

Post by miras » Thu Jul 17, 2003 12:45 pm

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

Post by bugzpodder » Thu Aug 07, 2003 2:05 pm

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.

Post Reply

Return to “Volume 100 (10000-10099)”