Discussion @ 1306. Sequence Median @ Timus Online Judge

Nazgul ( Ivan Nicolae ) Why dis program not work? I think it should get AC it gets WA [11] // Problem 1306. Sequence Median 25 Mar 2005 20:16

Why does this program not work?
here is the code:

var n,i:longint;
    nr:array[0..250000] of double;

procedure quick(li,ls:longint);
var i,j:longint;
    x,y:double;
begin
     i:=li; j:=ls; x:=nr[(li+ls) div 2];
     repeat
           while nr[i]<x do inc(i);
           while nr[j]>x do dec(j);
           if i<=j then
             begin
                  x:=nr[i]; nr[i]:=nr[j]; nr[j]:=x;
                  inc(i); dec(j);
              end;
     until i>j;
     if i<ls then quick(i,ls);
     if j>li then quick(li,j);
end;

begin
     readln(n);
     for i:=1 to n do readln(nr[i]);
     quick(1,n);
     if n=1 then writeln(nr[1] / 2 :0:1)
       else if n mod 2<>0 then writeln(nr[n div 2+1]:0:0)
       else writeln((nr[n div 2]+nr[n div 2+1]) / 2:0:1);

end.

Cybernetics Team Re: Why dis program not work? I think it should get AC it gets WA [10] // Problem 1306. Sequence Median 25 Mar 2005 21:12

Well...
- if you got a single number the median I think it's the number itself, don't you?
- you must be kidding with that 250k double array right?

Nazgul ( Ivan Nicolae ) Re: Why dis program not work? I think it should get AC it gets WA [9] // Problem 1306. Sequence Median 25 Mar 2005 22:18

Yes you are right, if there is a single number then the answer should be that number, but I stil get WA.( not compilation error)

Cybernetics Team Re: Why dis program not work? I think it should get AC it gets WA [8] // Problem 1306. Sequence Median 25 Mar 2005 22:51

Well, I must say that finding the bug in your program took me about one hour and tenths of submissions. I looked at the WA test, 5, and realize that your sorting wasn't ok, comparing to a bubble sort. So, studying your quicksort, I found that the flipping of nr[i] and nr[j] uses x as intermediate value, which is incorrect because x is used in the function furthermore. I wondered from the first time what was the use of that 'y' so... Are you thinking what I'm thinking? :)
And again, whats the idea with that 250k array? Or only testing brute force? :D

PS: you aren't at the ONI right now?

Edited by author 25.03.2005 23:03

Mustafa Re: Why dis program not work? I think it should get AC it gets WA [7] // Problem 1306. Sequence Median 25 Mar 2005 23:04

Thanks, I'm such an idiot, usually I use an y for the swaping, as you can see "am alocat pe y", but didn't use it. I guess I'm sorry I took 1 h an a halt of you'r tine. Thanks.

james007 Re: Why dis program not work? I think it should get AC it gets WA [6] // Problem 1306. Sequence Median 25 Mar 2005 23:27

This is my dirty code. So is mustafa. Sorry because I got mixed up in them.

Edited by author 25.03.2005 23:27

james007 Re: Why dis program not work? I think it should get AC it gets WA [5] // Problem 1306. Sequence Median 25 Mar 2005 23:28

Stil I get WA at test 1.

Cybernetics Team Re: Why dis program not work? I think it should get AC it gets WA [4] // Problem 1306. Sequence Median 25 Mar 2005 23:31

The first test is 1 1

Nazgul ( Ivan Nicolae ) Re: Why dis program not work? I think it should get AC it gets WA [3] // Problem 1306. Sequence Median 26 Mar 2005 01:07

And the answer should be 1. Exactly like my program outputs but my program stil gets WA.

Nazgul ( Ivan Nicolae ) Re: Why dis program not work? I think it should get AC it gets WA [1] // Problem 1306. Sequence Median 26 Mar 2005 11:45

How can I be at ONI. I am the 8-th grade, I'll be at ONI after 29th of March. Right now I am at ONIbyNET, for the 9th grade.

Tolstobrov_Anatoliy[Ivanovo SPU] Re: Why dis program not work? I think it should get AC it gets WA // Problem 1306. Sequence Median 19 Jun 2005 18:23

var n,i:longint;
nr:array[0..250000] of double;

procedure quick(li,ls:longint);
var i,j:longint;
x,y:double;
begin
i:=li; j:=ls; x:=nr[(li+ls) div 2];
repeat
while nr[i]<x do inc(i);
while nr[j]>x do dec(j);
if i<=j then
begin
x:=nr[i]; nr[i]:=nr[j]; nr[j]:=x; <== Change (x<=>y) :)
inc(i); dec(j);
end;
until i>j;
if i<ls then quick(i,ls);
if j>li then quick(li,j);
end;

begin
readln(n);
for i:=1 to n do readln(nr[i]);
quick(1,n);
if n=1 then writeln(nr[1] / 2 :0:1)
else if n mod 2<>0 then writeln(nr[n div 2+1]:0:0)
else writeln((nr[n div 2]+nr[n div 2+1]) / 2:0:1);
end.

And you got MLE!!!

Marek Sapota Re: Why dis program not work? I think it should get AC it gets WA // Problem 1306. Sequence Median 23 Aug 2006 01:45

Nazgul ( Ivan Nicolae ) wrote 26 March 2005 01:07

And the answer should be 1. Exactly like my program outputs but my program stil gets WA.

Answer should be 1.0!!!

Discussion of Problem 1306. Sequence Median