## 10041 - Vito's Family

Moderator: Board moderators

Tamagodzi
New poster
Posts: 22
Joined: Thu Apr 28, 2005 10:56 pm
My ACC program has same output

with some little modifications u will easy get ACC for prob 10057

Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria
Alright then. Thanks, Tamagodzi !

liqu
New poster
Posts: 2
Joined: Thu Aug 25, 2005 6:50 pm

### 10041 vito's family ~ Plez Help me ~ thax

I got a TLE result .

Here is my code :
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <iostream.h>
using namespace std;

int compare (const void * a, const void * b)
{
return ( *(int*)a - *(int*)b );
}

int main()
{
int n,i,r,j,k;
cin>>n;
for(i=1;i<=n;i++)
{
long min=0,tmp=0;
cin>>r;
int *vito;
vito=(int *)malloc(sizeof(int)*(r+1));
for(j=0;j<r;j++)
cin>>vito[j];
for(k=0;k<r;k++)
min+=vito[k];

qsort(vito,r,sizeof(int),compare);
for(j=vito[1];j<vito[r-1];j++)
{
tmp=0;
for(k=0;k<r;k++)
tmp+=abs(j-vito[k]);

if(tmp<min)min=tmp;
}
cout<<min<<endl;
}

}

Could someone help me with my problem ?
I have tried several data , all of them were solved within the time limit ,
so i can't find why my program cant be AC

tan_Yui
Experienced poster
Posts: 155
Joined: Sat Jul 10, 2004 12:41 am

### Re: 10041 vito's family ~ Plez Help me ~ thax

Code: Select all

``````        for(j=vito[1];j<vito[r-1];j++)
{
tmp=0;
for(k=0;k<r;k++)
tmp+=abs(j-vito[k]);

if(tmp<min)min=tmp;
}
cout<<min<<endl;
``````
This part 2-loop is not efficient.
Try to change the single-loop algorithm.

I think that the determine the median is efficient for this problem.
This can be implemented by single-loop.

And,

Code: Select all

``````int *vito;
vito=(int *)malloc(sizeof(int)*(r+1)); ``````
I think "int vito[499];" is enough to use instead of malloc.

Best regards.

Racevictor
New poster
Posts: 3
Joined: Mon Nov 29, 2004 12:14 pm

### 10041 vito's family ~ WA

My code:

#include<iostream>
#include<stdlib.h>
using namespace std;
int a[501],i,j,m,n,result;
int compare (const void * a, const void * b)
{
return ( *(int*)a - *(int*)b );
}
int main(){
cin>>n;
for(i=0;i<n;i++)
{
result = 0;
cin>>m;
for(j=0;j<m;j++)
cin>>a[j];
qsort (a,m, sizeof(int), compare);
for(j=0;j<m;j++)
result += (int)abs(double(a[j]-a[m/2]));
cout<<result<<endl;
}

return 0;
}

Thankyou !!

Racevictor
New poster
Posts: 3
Joined: Mon Nov 29, 2004 12:14 pm
AC la , thx

Munni
New poster
Posts: 9
Joined: Tue Jan 03, 2006 4:59 pm

### 10041 WA

i cant fix the prblm of my code.Probably i dont understand the algo.plz hlp me nd give some examples so tht i can understnd the alogo...

Code: Select all

``````[color=green][/color]
#include<stdio.h>
#include<iostream.h>
#include<stdlib.h>
int compare( const void *a, const void *b)
{
return( *(int *)a-*(int*)b);
}
int find_dis(int vito2[],int opt,int j)
{

int i,dis=0;
for(i=0;i<j;i++)
{
if(i==opt)
continue;
dis+=abs(vito2[i]-vito2[opt]);
}
return dis;
}

int main(void)
{

int test,i,r,vito[600],k,vito1[600],j,opt,dis;
cin>>test;
if(test!=EOF)
{
for(k=0;k<test;k++)
{
cin>>r;
dis=0;
for(i=0;i<r;i++)
{
cin>>vito[i];

}
qsort(vito,r,sizeof(int),compare);
vito1[0]=vito[0];
for(i=1,j=1;i<r;i++)
{
if(vito1[j-1]==vito[i])
continue;
vito1[j]=vito[i];
j++;

}
if(j==1)
{
cout<<dis;
cout<<"\n";

}

else  if((j%2)==0)
{
opt=(j/2)-1;
dis=find_dis(vito,opt,r);
cout<<dis;
cout<<"\n";

}
else
{
opt=j/2;
dis=find_dis(vito1,opt,j);
cout<<dis;
cout<<"\n";
}
}
}

return 0;

}

``````

mamun
A great helper
Posts: 286
Joined: Mon Oct 03, 2005 1:54 pm
Contact:
If you don't understand the algo, then search for this topic in the forum and you'll surely get it. This is what you should do before posting your problem. This problem is as simple as finding the median.

CGR
New poster
Posts: 4
Joined: Sun Oct 09, 2005 8:11 pm
Why WA?????

I'm using the median, I tried every input/output found in this forum, and it works for all of them.
This pb seems so easy..

My code :

Code: Select all

``````#include <stdio.h>

int compare (int*, int*);

main() {

int n_cases, n_relat;
int median, min;
int sum_dist;
int i,j;
int streets[510];

scanf("%d", &n_cases);

while (n_cases > 0) {

scanf("%d", &n_relat);

for (i=0;i<n_relat;i++) scanf("%d", &streets[i]);

qsort(streets, n_relat, sizeof(int), compare);

if (n_relat%2 == 1) {
median = streets[(n_relat-1)/2];
sum_dist = 0;
for (i=0;i<n_relat;i++)
sum_dist += abs(streets[i] - median);
printf("%d\n", sum_dist);
}
else {
min = 1000000;
for (i=streets[(n_relat/2)-1];i<=streets[(n_relat/2)];i++) {
sum_dist = 0;
for (j=0;j<n_relat;j++)
sum_dist += abs(streets[j] - i);
if (sum_dist < min) min = sum_dist;
}
printf("%d\n", min);
}

n_cases--;
}
}

int compare (int* a, int* b) {

if (*a > *b) return 1;
if (*a < *b) return -1;
return 0;
}``````
Could somebody help me ?

tickets
New poster
Posts: 1
Joined: Thu Mar 08, 2007 2:19 am
Hey Pal,
Test this set:
1
5
1 1 1 2 3

The medium doesn't work this case.
Sometimes brute force can happen
Rafael Borja

turcse143
Learning poster
Posts: 81
Joined: Wed May 09, 2007 9:59 pm
thanks i got ac by changing formula of difference
''I want to be most laziest person in the world''

yuziyu
New poster
Posts: 1
Joined: Sun Mar 16, 2008 11:25 am

### 10041 - Could someone tell me how to make a shorter runtime?

[/code]
#include <iostream>
#include <vector>
using namespace std;

int main()
{
int case_num = 0;

cin>>case_num;

vector<int>result(case_num,0);

for(int j=0;j<case_num;++j)
{

int relatives_num;
cin>>relatives_num;

int sum = 0;
vector<int>v(relatives_num,0);

for(int i=0;i<relatives_num;++i)
{
cin>>v;
}

sort(v.begin(),v.end());

for(int i=0;i<relatives_num/2;++i)
{
sum+=v[relatives_num-1-i]-v;
}

result[j]=sum;
}

for(int i=0;i<case_num;++i)
{
cout<<result<<endl;
}

return 0;

}

Code: Select all

``````
And this code takes  	0.090 runtime..
Could someone tell me the skills to make a program run faster?
Thank you!
``````

emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Contact:
By avoiding stl and cin, cout you can save some time.
And always try to use existing thread to post.

midobo
New poster
Posts: 5
Joined: Sat Jul 19, 2008 12:24 pm

### 10041 - Vito's Family(Runtime Error)

Can any one help me plz??
all problems i solved got RE
i don't know why
plz help me in this problem
this my code:
#include<stdio.h>
#include<stdlib.h>

int swap(int a[],int b)
{
int temp=0;
temp=a;
a=a[b+1];
a[b+1]=temp;
return *a;
}

int sort(int a[3000],int n)
{
for(int s=1;s<n;s++)
{
for(int s1=0;s1<n-1;s1++)
if(a[s1]>a[s1+1])
swap(a,s1);
}
return a[3000];
}

int main()
{
int n,dist,med,cases;
int a[3000]={0},c[100];
scanf("%d",&cases);
for(int i=0;i<cases;i++)
{
dist=0;
scanf("%d",&n);
for(int j=0;j<n;j++)
scanf("%d",&a[j]);

sort(a,n);
med=a[n/2];
for(int j1=0;j1<n;j1++)
dist+=abs(med-a[j1]);
c=dist;
}

for(int cas=0;cas<cases;cas++)
{
printf("%d\n",c[cas]);
}

exit(0);
return 0;
}

Obaida
A great helper
Posts: 380
Joined: Wed Jan 16, 2008 6:51 am

### Re: 10041 - Vito's Family

Remove the exit(0); function. This is not valid.
Hope you get Accepted & remove the code.
try_try_try_try_&&&_try@try.com
This may be the address of success.