Naruto has recently joined the Ninja Academy for higher education, while filling the admission form he is required to choose minimum $X$ subjects out of a list of $N$ subjects. He is not very interested in studies but wants to get a good overall CPI. However, every subject has a different weightage/credit. The credit (denoted as $C$_{i}) of a particular course is equal to the position in which it appears in the subject list, i.e, the first course has a credit=1, the second course has a credit=2, and so on.
Naruto knows his capabilities, and so he has come up with the scores ($S$_{i})  he can achieve in every course. He wants to maximise his CPI, which can be calculated as the weighted mean of all the subjects taken, denoted as
__Sum(C_{i}*S_{i})/Sum(C_{i})__ for all i s.t Naruto has taken up course i

------ Input: ------

First line will contain $T$, number of testcases. Then the testcases follow. 
First line of every test case contains two integers, $N$ and $X$
Next line of the test case contains $N$ space separated integers S_{i}, denoting the score he can get in every subject

------ Output: ------
For each testcase, output in a single line the maximum cpi he can get after choosing the subjects. Your output will be considered correct if it has an absolute error of less than 10^{-6}.

------ Constraints  ------
$1 ≤ T ≤ 10$
$1 ≤ N ≤ 1000$
$1 ≤ X ≤ N$
$1 ≤ S$_{i}$   ≤ 10000$

------ Sample Input: ------
1  
5 2  
50 40 30 20 10  

------ Sample Output: ------
43.3333333333

------ Explanation: ------
He can achieve the max credit by picking the first two subjects, which produces a CPI of (50 * 1+40 * 2)/(1+2) = 43.333333333

Difficulty: VERY_HARD
Tags: Sorting

Complete search
Skill types: Sorting

Complete search

Starter code:

Solutions:
t = int(input())
for r in range(t):
	[n, x] = [int(y) for y in input().split()]
	e1 = [int(u) for u in input().split()]
	e = [[e1[x], x + 1] for x in range(n)]
	p = []
	x1 = 0
	c1 = 0
	for x2 in range(n):
		if x2 < x:
			y2 = 0
			for x3 in e:
				y1 = (x1 * c1 + x3[1] * x3[0]) / (c1 + x3[1])
				if y1 > y2:
					temp = x3
					temp1 = y1
					y2 = y1
			e.remove(temp)
			x1 = temp1
			c1 += temp[1]
	print(x1)


def ii():
	return int(input())

def mi():
	return map(int, input().split())

def li():
	return list(mi())

def check(A, n, k):
	num = 0
	dem = 0
	mx = 0
	AA = [0] * n
	(a, b) = (0, 0)
	for i in range(n):
		for j in range(n):
			if mx < (A[i] + A[j]) / (i + j + 2) and i != j:
				mx = (A[i] + A[j]) / (i + j + 2)
				a = i
				b = j
	num += A[a] + A[b]
	dem += a + b + 2
	AA[a] = 1
	AA[b] = 1
	x = 2
	while x < k:
		(a, b) = (0, 0)
		mx = 0
		for i in range(n):
			if AA[i] == 0:
				temp = (num + A[i]) / (dem + i + 1)
				if mx < temp:
					mx = temp
					a = A[i]
					b = i + 1
		x += 1
		num += a
		dem += b
		AA[b - 1] = 1
	return mx
for _ in range(ii()):
	(n, k) = mi()
	A = li()
	if k == 1:
		print(max(A))
	else:
		for i in range(n):
			A[i] = A[i] * (i + 1)
		mx = check(A, n, k)
		print('{0:.10f}'.format(mx))


for _ in range(int(input())):
	(n, x) = [int(i) for i in input().split()]
	s = [int(i) for i in input().split()]
	cg = s[0]
	credits = 1
	for i in range(1, n):
		if s[i] > cg:
			cg = s[i]
			credits = i + 1
	s[credits - 1] = 0
	while x > 1:
		best = 0
		for i in range(n):
			if s[i] != 0:
				temp = (cg * credits + (i + 1) * s[i]) / (credits + 1 + i)
				if temp > best:
					best = temp
					val = i
		credits += val + 1
		cg = best
		s[val] = 0
		x -= 1
	print(cg)


t = int(input())
for _ in range(t):
	(n, x) = [int(i) for i in input().split()]
	a = [int(i) for i in input().split()]
	s = 0
	d = 0
	for i in range(x):
		max = 0
		dt = 0
		for j in range(n):
			if a[j] != 0 and (s + a[j] * (j + 1)) / (d + j + 1) > max:
				max = (s + a[j] * (j + 1)) / (d + j + 1)
				dt = j
		s += a[dt] * (dt + 1)
		a[dt] = 0
		d += dt + 1
	print('{:.10f}'.format(s / d))