## 10041 - Vito's Family

Moderator: Board moderators

My ACC program has same output

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

Posts: 22
Joined: Thu Apr 28, 2005 10:56 pm

Alright then. Thanks, Tamagodzi !

Sedefcho
A great helper

Posts: 375
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

### 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
liqu
New poster

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

### 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.
tan_Yui
Experienced poster

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

### 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
Racevictor
New poster

Posts: 3
Joined: Mon Nov 29, 2004 12:14 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;            }`
Munni
New poster

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

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.
mamun
A great helper

Posts: 286
Joined: Mon Oct 03, 2005 1:54 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 ?
CGR
New poster

Posts: 4
Joined: Sun Oct 09, 2005 8:11 pm

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
tickets
New poster

Posts: 1
Joined: Thu Mar 08, 2007 2:19 am

thanks i got ac by changing formula of difference
''I want to be most laziest person in the world''
turcse143
Learning poster

Posts: 81
Joined: Wed May 09, 2007 9:59 pm

### 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[i];
}

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

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

result[j]=sum;
}

for(int i=0;i<case_num;++i)
{
cout<<result[i]<<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!`
yuziyu
New poster

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

By avoiding stl and cin, cout you can save some time.
And always try to use existing thread to post.

emotional blind
A great helper

Posts: 383
Joined: Mon Oct 18, 2004 8:25 am

### 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[b];
a[b]=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[i]=dist;
}

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

exit(0);
return 0;
}
midobo
New poster

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

### 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.
Obaida
A great helper

Posts: 380
Joined: Wed Jan 16, 2008 6:51 am