10041 - Vito's Family

[Whinii F.]

From my sent mailbox I find the following:

So, for the one-dimensional problem:
If there are n places sorted along x-axis:
a) if n = 2x (where x is a natural number), the appropriate meeting place can be anywhere within range coordinate[x] ~ coordinate[x+1] (inclusive). Why? because in this range, "each move of the m.p one cell" will increase cost for x places by 1, decrease cost for x places by 1, so the total cost would be the same. If it tries to go out from the range(like meeting in coordinate[x]-1), it will increase cost for x+1 places and decrease cost for x-1 places by 1. So in that case the total cost will be increased.
b) if n=2x+1 ? You'll easily see that the m.p. should be placed in coordinate[x+1] if you observe the above.

(m.p. stands for meeting point)

Hope I helped?

[bugzpodder]

hmm i was looking for something a little more rigorous than that.
if we look at odd n=2k+1 (i am gonna use k just so it doesnt confuse with x)

then if we meet at coord[k+1]
then f(x)=Sum |x-ai|=x-a1+x-a2+...+x-ak+(x-a_(k+1))+a_(k+1)-x+...+a_n-x
=a_(k+2)-a1+a_(k+3)-a2+...+a_(2k+1)-a_k

you are right in saying:

If it tries to go out from the range(like meeting in coordinate[x]-1), it will increase cost for x+1 places and decrease cost for x-1 places by 1.

but i dont see how this proves the general case.

[Whinii F.]

If you understand that then you can easily prove that to meet at coord[k+p] will always cost more than meeting at coord[k+p-1] where p >= 1.
The opposite part would be the same. Try it on your own

[bugzpodder]

maybe you did not explain clearly and i did not understand but thx anyways. Allan's dad showed me this induction proof cleared things up for me. thanks Allan!

[babor]

Hai, at first sort the aray[];
then find median for even or odd number of total thing.
then use median to calculate.

[Niaz Morshed]

One of the important property of the median is the distance from any median (in case of even we get two medians) to each element is equal. So u need not to find the distance from each median or from the mean of the median. I have seen that many persons tried to find the mean in the median So don't go for these. Just follow this algorithm,
[cpp] 1. Sort the elements.
2. Find the median. Always take the first one. (its enough)
3. Find the distance from median to others using the formula given in problem.
4. That's enough . [/cpp]

[problem]

why runtime error.plz give me the correct solution.i use insertion sort.first sort all data and find the solution.if its wrong give me some tricks also.

[c]


#include<string.h>
#include<math.h>
#include<stdio.h>
void main()
{
unsigned long int n,m,sum=0,x,q,l;
unsigned long int array[3000]={0}; /*should have to increase array to 30010*/

while(scanf("%lu",&x)!=EOF)
{
for(q=0;q<x;q++)
{
int i=0,k;
while(scanf("%lu",&n)!=EOF)
{

k=i-1;

while(n<array[k]&&k>=0)
{
array[k+1]=array[k];
--k;
}
array[k+1]=n;
if(l==m-1)break;
++i;
}

for(int j=0;j<i-1;j++)
{
sum=sum+(array[j+1]-array[j]);
}
printf("%lu\n",sum);
n=0;
i=0;
sum=0;
}
}

}[\c]

[Jer]

i think it want us to ouput the N/2's in the sorted data (0~N).
i use the partition function to find it.
but i got WA much time .
Can anyone help me ?
or provided some test data....thanks.~~

[sohel]

I think it want us to ouput the N/2's in the sorted data (0~N).

Hi Jer,
You are right about the fact that you have to find N/2 ( median that is )
for this problem, but you are not asked to output this.
You have to output the sum of the distances from ( N/2th to all other houses).
Hope it helps.

[Jer]

Oh , it's true....
the sample output confused me.
thank you very much,sohel.

[zeka]

I have tested my code with ins/outs other guys posted here.All worked perfect on my PC but wrong answer again & again! I don't know what does that robot expect my program to output.Can any one tell me why I still get WA? Here's my code:
[c]
#include <stdio.h>

long int testcases,a,b,c[100],i,k,j,streets[500],relatives;
main() {

scanf("%d",&testcases);

for (j=0;j<testcases;j++) {
scanf("%d",&relatives);

for (k=0;k<relatives;k++) {
scanf("%d",&streets[k]);
}

for (k=0;k<relatives;k++) {
a=streets[k];

for (i=k+1;i<relatives;i++) {

if (streets<a) {
b=a;
a=streets;
streets=b;
streets[k]=a;
}
}
}
if (relatives%2==0)
k=relatives/2-1;
else
k=(relatives-1)/2;
a=streets[k];
for (k=0,b=0;k<relatives;k++) {
if (streets[k]>a)
b+=streets[k]-a;
else
b+=a-streets[k];
}

c[j]=b;

}

for (j=0;j<testcases;j++)
printf("%d\n",c[j]);

return 0;
}
[/c]
p.s.
Maybe someone could send me a working code to compare with (i mean that code which judge considers correct) .Thanx!

[_.B._]

Greetings!.
Need some help here.
My I/O is this:

Input:

Code: Select all

11
10 2 2 4 2 2 2 2 2 2 2
3 6 4 2
9 2 4 6 4 4 4 4 4 4
3 100 10 1
7 5 1 7 1 9 1 10
3 1 1 8
4 3 1 5 7
10 30 25 15 1 1 1 23 23 90 10
499 1 1 1 1 1 1 1 1 1 1 1 29999 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
100 29999 29999 29999 29999 1 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999
5 100 1 1 1 1

Output:

Code: Select all

2
4
4
99
23
7
8
163
29998
29998
99

I have no idea of what's wrong with my code. I made it in Pascal. Should I post it here?.
Is there ANY criticla I/O??.
What's the output for?:

Code: Select all

3
1 23
2 8 8
499 29999 29998 29997 29996 29995 29994 29993 29992 29991 29990 29989 29988 29987 29986 29985 29984 29983 29982 29981 29980 29979 29978 29977 29976 29975 29974 29973 29972 29971 29970 29969 29968 29967 29966 29965 29964 29963 29962 29961 29960 29959 29958 29957 29956 29955 29954 29953 29952 29951 29950 29949 29948 29947 29946 29945 29944 29943 29942 29941 29940 29939 29938 29937 29936 29935 29934 29933 29932 29931 29930 29929 29928 29927 29926 29925 29924 29923 29922 29921 29920 29919 29918 29917 29916 29915 29914 29913 29912 29911 29910 29909 29908 29907 29906 29905 29904 29903 29902 29901 29900 29899 29898 29897 29896 29895 29894 29893 29892 29891 29890 29889 29888 29887 29886 29885 29884 29883 29882 29881 29880 29879 29878 29877 29876 29875 29874 29873 29872 29871 29870 29869 29868 29867 29866 29865 29864 29863 29862 29861 29860 29859 29858 29857 29856 29855 29854 29853 29852 29851 29850 29849 29848 29847 29846 29845 29844 29843 29842 29841 29840 29839 29838 29837 29836 29835 29834 29833 29832 29831 29830 29829 29828 29827 29826 29825 29824 29823 29822 29821 29820 29819 29818 29817 29816 29815 29814 29813 29812 29811 29810 29809 29808 29807 29806 29805 29804 29803 29802 29801 29800 29799 29798 29797 29796 29795 29794 29793 29792 29791 29790 29789 29788 29787 29786 29785 29784 29783 29782 29781 29780 29779 29778 29777 29776 29775 29774 29773 29772 29771 29770 29769 29768 29767 29766 29765 29764 29763 29762 29761 29760 29759 29758 29757 29756 29755 29754 29753 29752 29751 29750 29749 29748 29747 29746 29745 29744 29743 29742 29741 29740 29739 29738 29737 29736 29735 29734 29733 29732 29731 29730 29729 29728 29727 29726 29725 29724 29723 29722 29721 29720 29719 29718 29717 29716 29715 29714 29713 29712 29711 29710 29709 29708 29707 29706 29705 29704 29703 29702 29701 29700 29699 29698 29697 29696 29695 29694 29693 29692 29691 29690 29689 29688 29687 29686 29685 29684 29683 29682 29681 29680 29679 29678 29677 29676 29675 29674 29673 29672 29671 29670 29669 29668 29667 29666 29665 29664 29663 29662 29661 29660 29659 29658 29657 29656 29655 29654 29653 29652 29651 29650 29649 29648 29647 29646 29645 29644 29643 29642 29641 29640 29639 29638 29637 29636 29635 29634 29633 29632 29631 29630 29629 29628 29627 29626 29625 29624 29623 29622 29621 29620 29619 29618 29617 29616 29615 29614 29613 29612 29611 29610 29609 29608 29607 29606 29605 29604 29603 29602 29601 29600 29599 29598 29597 29596 29595 29594 29593 29592 29591 29590 29589 29588 29587 29586 29585 29584 29583 29582 29581 29580 29579 29578 29577 29576 29575 29574 29573 29572 29571 29570 29569 29568 29567 29566 29565 29564 29563 29562 29561 29560 29559 29558 29557 29556 29555 29554 29553 29552 29551 29550 29549 29548 29547 29546 29545 29544 29543 29542 29541 29540 29539 29538 29537 29536 29535 29534 29533 29532 29531 29530 29529 29528 29527 29526 29525 29524 29523 29522 29521 29520 29519 29518 29517 29516 29515 29514 29513 29512 29511 29510 29509 29508 29507 29506 29505 29504 29503 29502 29501

Thanks in advance.

[shamim]

The input/output you provided are correct.
Better post your code to see what is wrong.

[_.B._]

Greetings!.
Thanks for checking shamin!.
Here's the code:
[pascal]Accepted[/pascal]

The code is a bit extense (less extense thanks to little joey), since I've had to modify it a lot
Hope you people can understand it.
I've got more than 15 WAs for this problem.
Thanks in advance, even for taking the time to read the code

[little joey]

Hm.
I solved this problem in Pascal only using the function read(), so there's no need for C++.

[pascal]program p10041;

var
number:array[1..1000] of integer;
numbers:integer;

procedure XXXXXXXXXXX;
{ CODE REMOVED }

var
cases,caseno,i,median,distance:integer;
begin
read(cases);
for caseno:=1 to cases do begin
read(numbers);
for i:=1 to numbers do read(number);
{ CODE REMOVED }
writeln(distance);
end;
end.
[/pascal]
Spoilers removed. (Oops, I left one in...)

Did you read the previous postings on this problem? They almost give it away.