EC_ESTA - Statistics Applied
In this problem we will be looking for medians of data set. Median is the central element in ordered data group. For example: for the set {2, 6, 3, 3, 2} the median would be 3. In general, if we have n elements {a1, a2, a3 ... an}, we define the median as element a(n+1)/2 if n is odd and (an/2+an/2+1)/2 otherwise.
You will be given N numbers and you must calculate N medians. i-th median is taken on the subset [a1, a2, a3 ... ai] for 1 ≤ i ≤ N.
Input
The first line contains the number of test cases. Each case consists of an integer N (1 ≤ N ≤ 100000). N integers ai (0 ≤ ai < 231) follow, elements in data set.
Output
For each case, print N lines with the medians. If the result is non-integral, print the exact value using decimal point (see example).
Example
Input: 2 4 3 5 7 3 2 3 4 Output: 3 4 5 4 3 3.5
hide comments
asifalim:
2020-11-29 11:03:33
If even length then if(median&1) after "." print only 5. This mistake lost my 2 attempts |
|
shobhit469:
2020-03-28 14:27:38
check your output for
|
|
harshit2202:
2018-08-11 08:28:31
nice ques. |
|
Eddy Cael:
2017-05-11 15:53:53
there are two solutions: multiset and also priority_queue. :D |
|
dwij28:
2016-10-01 23:14:49
TLE for heap ? Seriously ? |
|
ravi:
2016-06-25 14:44:40
stl prority_queue gives tle ,take care of case when we have to consider middle two elements it doesnot fit in int. |
|
yash agarwal:
2015-06-03 16:22:54
my id is :14384729
|
|
Kunal:
2015-04-18 21:26:55
Shouldn't the fourth output be 6 ?
|
|
newbie:
2015-03-15 21:05:58
since median is taken in sorted list.... |
|
newbie:
2015-03-15 21:04:44
i think second output should be 3 as (3+3)/2=3 & not 4
|
Added by: | Eddy Cael |
Date: | 2013-10-26 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | C C++ 4.3.2 CPP JAVA |
Resource: | COMPETENCIA CCBOL2013 |