10041 - Vito's Family

[Tamagodzi]

My ACC program has same output

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

[Sedefcho]

Alright then. Thanks, Tamagodzi !

[liqu]

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]

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]

Please help :

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]

AC la , thx

[Munni]

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]

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]

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]

Hey Pal,
Test this set:
1
5
1 1 1 2 3

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

[turcse143]

thanks i got ac by changing formula of difference

[yuziyu]

[/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!


[emotional blind]

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

[midobo]

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;
}

[Obaida]

Remove the exit(0); function. This is not valid.
Hope you get Accepted & remove the code.