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

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

Post by Tamagodzi » Thu Apr 28, 2005 11:09 pm

My ACC program has same output

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

User avatar
Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

Post by Sedefcho » Fri Apr 29, 2005 1:24 am

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

Post by liqu » Thu Aug 25, 2005 7:28 pm

I got a TLE result . :cry:

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

Post by tan_Yui » Mon Aug 29, 2005 5:01 am

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

Post by Racevictor » Wed Sep 21, 2005 5:13 pm

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

Post by Racevictor » Wed Sep 21, 2005 5:59 pm

AC la , thx

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

10041 WA

Post by Munni » Mon Jan 09, 2006 7:04 pm

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
Location: Bangladesh
Contact:

Post by mamun » Mon Jan 09, 2006 8:16 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.

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

Post by CGR » Mon Sep 18, 2006 8:55 pm

Why WA????? :cry:

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

Post by tickets » Thu Mar 08, 2007 2:23 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 :wink:
Rafael Borja

turcse143
Learning poster
Posts: 81
Joined: Wed May 09, 2007 9:59 pm
Location: (CSE,DU) Dhaka,Bangladesh

Post by turcse143 » Fri Dec 28, 2007 11:22 pm

:D 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?

Post by yuziyu » Sun Mar 16, 2008 11:29 am

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

User avatar
emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Location: Bangladesh
Contact:

Post by emotional blind » Sun Mar 16, 2008 2:02 pm

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)

Post by midobo » Mon Jul 28, 2008 7:53 pm

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
Location: (BUBT) Dhaka,Bagladesh.

Re: 10041 - Vito's Family

Post by Obaida » Thu Jul 31, 2008 11:30 am

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

Post Reply

Return to “Volume 100 (10000-10099)”