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

raj
Learning poster
Posts: 78
Joined: Fri Feb 15, 2013 5:39 pm

Re: 10041 - Vito's Family

Post by raj » Tue Mar 05, 2013 12:28 am

1
10 30 25 15 1 1 1 23 23 90 10
for this WHY THE OUTPUT BECOMES 163 INSTEAD OF 211??????????????
PLEASE ANYONE TELL ME????? :(

lbv
Experienced poster
Posts: 128
Joined: Tue Nov 29, 2011 8:40 am

Re: 10041 - Vito's Family

Post by lbv » Tue Mar 05, 2013 2:47 am

raj wrote:1
10 30 25 15 1 1 1 23 23 90 10
for this WHY THE OUTPUT BECOMES 163 INSTEAD OF 211??????????????
PLEASE ANYONE TELL ME????? :(
Take your time to carefully read the problem statement, and then the previous messages from this forum thread. You should come to realize that Vito should locate his house in a street that is the median of all the numbers given in the input.

For the set of integers { 30 25 15 1 1 1 23 23 90 10 }, the median will be 19 (although any integer between 15 and 23 will work equally well). If you add all the distances from each street to the median, your result will be 163. If you try any other number outside the range [ 15 : 23 ] for Vito's house, you'll notice that the result will be a bigger number, so 163 is the optimal answer.

P.S. As you may know, writing something in ALL CAPS is usually interpreted as "shouting". I'd suggest you try to avoid that in a forum like this one.

raj
Learning poster
Posts: 78
Joined: Fri Feb 15, 2013 5:39 pm

Re: 10041 - Vito's Family

Post by raj » Thu Mar 07, 2013 1:46 am

:@ lbv i am extremely sorry for mistakes
i didnt know how to get medians but now i know it :D
but one thing i can not understand why sometimes MEDIAN doesnt work??? :(
can you please explain... :)

lbv
Experienced poster
Posts: 128
Joined: Tue Nov 29, 2011 8:40 am

Re: 10041 - Vito's Family

Post by lbv » Thu Mar 07, 2013 9:22 pm

raj wrote:i am extremely sorry for mistakes
It's okay, we all make mistakes; the important thing is to learn from them :).
raj wrote: but one thing i can not understand why sometimes MEDIAN doesnt work??? :(
can you please explain... :)
I'm not sure what you mean by "median doesn't work". Are you referring to this problem? Do you have an example in mind? If you do, please share it, but carefully check it again. Using the median should always give you the right answer for this problem, so if it doesn't for some reason, it might be a subtle bug in your code.

raj
Learning poster
Posts: 78
Joined: Fri Feb 15, 2013 5:39 pm

Re: 10041 - Vito's Family

Post by raj » Sat Mar 09, 2013 1:29 am

sorry sir... :)
median works all the time.... :D
i saw a previous post the i think median doesnt work...........
now its accepted... thanks :)

mmoonn
New poster
Posts: 1
Joined: Sun Jul 07, 2013 6:02 am

Re: 10041 - Vito's Family

Post by mmoonn » Sun Jul 07, 2013 6:14 am

i want to know what is wrong with my code plz,it gives WA

Code: Select all

import java.util.Arrays;
import java.util.Scanner;

public class Main{

	public static int[] streets;

	private static int getDis(int mid) {
		int dis = 0;
		for (int i = 0; i < streets.length; i++) {
			dis += Math.abs(mid - streets[i]);
		}
		return dis;
	}

	public static void main(String[] args) {
		// get median
		Scanner sc = new Scanner(System.in);
		int tests = sc.nextInt();
		int[][] input = new int[tests][];
		sc.nextLine();
		for (int i = 0; i < tests; i++) {
			String[] sp = sc.nextLine().trim().split(" ");
			input[i] = new int[sp.length - 1];
			for (int j = 1; j < sp.length; j++) {
				input[i][j - 1] = Integer.parseInt(sp[j]);
			}
		}

		// evaluate
		for (int i = 0; i < input.length; i++) {
			int mid = 0;
			streets = input[i];
			for (int j = 0; j < input[i].length; j++) {
				mid += input[i][j];
			}
			mid = mid / input[i].length;
			int temp = mid;
			Arrays.sort(streets);
			int min = getDis(mid);
			int j = 0;
			while (j < streets.length) {
				mid += 1;
				int x = getDis(mid);
				if (x < min)
					min = x;
				else
					break;
				j++;
			}
			j = 0;
			mid = temp;
			while (j < streets.length) {
				mid -= 1;
				int x = getDis(mid);
				if (x < min)
					min = x;
				else
					break;
				j++;
			}

			System.out.println(min);
		}
	}
}


brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10041 - Vito's Family

Post by brianfry713 » Mon Jul 08, 2013 11:26 pm

Input:

Code: Select all

1
6 1 1 1 1 1000 1000
Output should be 1998
Check input and AC output for thousands of problems on uDebug!

Orni Noor
New poster
Posts: 1
Joined: Mon Dec 30, 2013 1:02 am
Location: Dhaka, Bangladesh

10041 - Vito's Family

Post by Orni Noor » Mon Dec 30, 2013 1:19 am

I cannot understand why I am getting RUNTIME ERROR in my code. Can anyone please help??? :(

Code: Select all

#include<stdio.h>
#include<stdlib.h>
int compare(const void* p1, const void* p2)
{
    if (*(long*)p1 < *(long*)p2)
    {
    return (-1);
    }
    if(*(long*)p1==*(long*)p2)
    {
    return (0);
    }
    if(*(long*)p1> *(long*)p2)
    {
    return (1);
    }
}
int main()
{
    long n;
    int s,r,i,j,k;
while((scanf("%ld",&n))==1)
{
    scanf("%d",&s);
    long a[500],d[500];
   for(i=0;i<s;i++)
    {
    scanf("%ld",&a[i]);
    }
qsort(a,s,sizeof(long),compare);
long median,sum=0;
if(s%2!=0)
{
    i=(s+1)/2;
    median=a[i-1];
}
else if(s%2==0)
{
    i=s/2;
    j=(s/2)+1;
    median=(a[i-1]+a[j-1])/2;
}
for(k=0;k<s;k++)
{
  d[k]=median-a[k];
  if(d[k]<0)
  {
    d[k]=-d[k];
  }
  sum=sum+d[k];
}
printf("%ld\n",sum);
}
return 0;
}
Last edited by brianfry713 on Tue Nov 18, 2014 9:45 pm, edited 1 time in total.
Reason: Added code blocks

User avatar
uDebug
A great helper
Posts: 475
Joined: Tue Jul 24, 2012 4:23 pm

Re: 10041 - Vito's Family

Post by uDebug » Wed Jan 01, 2014 1:39 pm

Here's some input / output I culled from this thread and that I found useful when testing / debugging.

Input:

Code: Select all

9
2 2 4 
3 2 4 6
6 11 2 1 6 5 11
6 7 8 2 3 6 1
6 1 1 1 1 1000 1000
4 1 2 4 5
10 30 25 15 1 1 1 23 23 90 10
5 1 1 1 2 3 
16 5 49 12 23 29 100 44 47 69 41 23 12 11 6 2 62
AC Output:

Code: Select all

2
4
20
15
1998
6
163
3
347
Check input and AC output for over 7,500 problems on uDebug!

Find us on Facebook. Follow us on Twitter.

User avatar
uDebug
A great helper
Posts: 475
Joined: Tue Jul 24, 2012 4:23 pm

Re: 10041 - Vito's Family

Post by uDebug » Wed Jan 01, 2014 2:11 pm

Orni Noor wrote:I cannot understand why I am getting RUNTIME ERROR in my code. Can anyone please help??? :(
First thing, if you want people to read your code, use the code tags. It improves readability.

Next, your code is going off bounds since you aren't reading in the input correctly.

Since we know how many cases are going to be there, this line

Code: Select all

while((scanf("%ld",&n))==1)
needs to be changed to something like

Code: Select all

/* Read in the number of cases */
scanf("%ld",&n);
/* Process each case */	
for(x = 0; x < n; x++) 
{...
I've made the changes to your program here.
http://pastebin.com/hmcJrDcp
It compiles and runs just fine.
Check input and AC output for over 7,500 problems on uDebug!

Find us on Facebook. Follow us on Twitter.

sejan
New poster
Posts: 6
Joined: Sun Nov 16, 2014 8:32 pm

Re: 10041 - Vito's Family

Post by sejan » Tue Nov 18, 2014 7:09 pm

why WA?

Code: Select all

ACCEPTED THANK YOU
:D
Last edited by sejan on Wed Nov 19, 2014 3:43 pm, edited 1 time in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10041 - Vito's Family

Post by brianfry713 » Tue Nov 18, 2014 9:53 pm

Make the initial value of temp bigger.
#include <limits.h>
int temp = INT_MAX;
Check input and AC output for thousands of problems on uDebug!

mpmohi
New poster
Posts: 13
Joined: Wed Feb 26, 2014 10:15 pm

Re: 10041 - Vito's Family

Post by mpmohi » Sat Nov 22, 2014 11:51 pm

lbv wrote:
raj wrote:1
10 30 25 15 1 1 1 23 23 90 10
for this WHY THE OUTPUT BECOMES 163 INSTEAD OF 211??????????????
PLEASE ANYONE TELL ME????? :(
Take your time to carefully read the problem statement, and then the previous messages from this forum thread. You should come to realize that Vito should locate his house in a street that is the median of all the numbers given in the input.

For the set of integers { 30 25 15 1 1 1 23 23 90 10 }, the median will be 19 (although any integer between 15 and 23 will work equally well). If you add all the distances from each street to the median, your result will be 163. If you try any other number outside the range [ 15 : 23 ] for Vito's house, you'll notice that the result will be a bigger number, so 163 is the optimal answer.

P.S. As you may know, writing something in ALL CAPS is usually interpreted as "shouting". I'd suggest you try to avoid that in a forum like this one.

though it is very late but how the Medin here can be 19 ?

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10041 - Vito's Family

Post by brianfry713 » Wed Nov 26, 2014 2:42 am

For the set of integers { 1 1 1 10 15 23 23 25 30 90 }, the median will be 19 = (15 + 23) / 2
Check input and AC output for thousands of problems on uDebug!

mpmohi
New poster
Posts: 13
Joined: Wed Feb 26, 2014 10:15 pm

Re: 10041 - Vito's Family

Post by mpmohi » Wed Nov 26, 2014 7:53 am

Thanks brainfry713 :)

Post Reply

Return to “Volume 100 (10000-10099)”