Taru likes reading. Every month he gets a copy of the magazine "BIT". The magazine contains information about the latest advancements in technology.  Taru 

reads the book at night and writes the page number to which he has read on a piece of paper so that he can continue from there the next day. But sometimes 

the page number is not printed or is so dull that it is unreadable.  To make matters worse Taru's brother who is really naughty tears of some of the pages of 

the Magazine and throws them in the dustbin. He remembers the number of leaves he had torn but he does not remember which page numbers got removed. When Taru 

finds this out he is furious and wants to beat him up. His brother apologizes, and says he won't ever do this again. But Taru did not want to be easy on him 

and he says "I will leave you only if you help me find the answer to this. I will tell you how many pages (Printed sides) were there in the Magazine plus the 

pages on which the page numbers were not printed. You already know the number of leaves you tore (T). Can you tell me the expected sum of the page numbers 

left in the Magazine?" Taru's brother replied "huh!! This is a coding problem". Please help Taru's brother.

Note: The magazine is like a standard book with all odd page numbers in front and the successive even page number on its back. If the book contains 6 pages, 

Page number 1 and Page number 2 are front and back respectively. Tearing a leaf removes both the front and back page numbers.

------ Input ------ 

The first line contains the number of test cases t. 3t lines follow. The first line of each test case contains the number of pages (printed sides) in the 

book. The second line's first integer is F, F integers follow which tell us the numbers of the page numbers not printed. The third line contains a single integer telling us the number of leaves Taru's brother tore.

------ Output ------ 

Output one real number correct up to 4 decimal digits which is equal to the expected sum of the page numbers left in the book.

------ Constraints ------ 

Number of printed Sides≤2000. All other values abide by the number of printed sides.

----- Sample Input 1 ------ 
2
10
2 1 2
2
10
1 8
0
----- Sample Output 1 ------ 
31.2000
47.0000

Source: codechef | Difficulty: MEDIUM
Tags: Data structures

Mathematics

Probability


Solutions:
for _ in range(int(input())):
	pages = int(input())
	F = list(map(int, input().split()))
	torn_leaves = int(input())
	total = pages * (pages + 1) / 2 - (sum(F) - F[0])
	if pages & 1:
		pages = pages // 2 + 1
	else:
		pages = pages // 2
	ans = round(total * (pages - torn_leaves) / pages, 4)
	print('{:.4f}'.format(ans))


for _ in range(int(input())):
	n = int(input())
	s = n * (n + 1) / 2
	l = list(map(int, input().split()))[1:]
	t = int(input())
	for i in l:
		s -= i
	n = (n + 1) // 2
	res = (n - t) / n * s
	print('%.4f' % res)


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	x = n * (n + 1) / 2
	for j in range(1, l[0] + 1):
		x -= l[j]
	f = int(input())
	n = int((n + 1) / 2)
	x -= x * f / n
	print('%.4f' % x)


t11 = int(input())
for i in range(t11):
	n01 = int(input())
	l01 = list(map(int, input().split()))
	x11 = n01 * (n01 + 1) / 2
	for i in range(1, l01[0] + 1):
		x11 = x11 - l01[i]
	f22 = int(input())
	n01 = int((n01 + 1) / 2)
	x11 = x11 - x11 * f22 / n01
	print('%.4f' % x11)


tests = int(input())
for i in range(tests):
	pages = int(input())
	arr = list(map(int, input().split()))
	tore = int(input())
	total = pages * (pages + 1) // 2 - sum(arr[1:])
	if pages & 1:
		pages = pages // 2 + 1
	else:
		pages = pages // 2
	ans = round(total * (pages - tore) / pages, 4)
	print('{:.4f}'.format(ans))


t = int(input())
for _ in range(t):
	n = int(input())
	sum = n * (n + 1) / 2
	ls = list(map(int, input().split()))[1:]
	for i in ls:
		sum -= i
	m = int(input())
	n = (n + 1) // 2
	ans = (n - m) / n * sum
	print('%.4f' % ans)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	r = int(input())
	(s, t) = (n * (n + 1) / 2, (n + 1) // 2)
	for i in range(1, a[0] + 1):
		s -= a[i]
	s = s * (t - r) / t
	print('%.4f' % s)


T = int(input())
for i in range(T):
	N = int(input())
	S = N * (N + 1) / 2
	L = input().split()
	L.pop(0)
	R = S - sum([int(x) for x in L])
	D = float(input())
	Result = (1.0 - D / ((N + 1) // 2)) * R
	Result = round(Result, 4)
	print('{:.4f}'.format(Result))


t = int(input())
for _ in range(t):
	p = int(input())
	l = list(map(int, input().split()))
	f = int(l[0])
	l = l[1:]
	tore = int(input())
	if p % 2 == 0:
		page = p // 2
	else:
		page = p // 2 + 1
	print(f'{(sum([i for i in range(1, p + 1)]) - sum(l)) * (page - tore) / page:.4f}')


T = int(input())
for x in range(T):
	p = int(input())
	f = list(map(int, input().split()))
	t = int(input())
	tot = p * (p + 1) // 2 - sum(f[1:])
	if p & 1:
		p = p // 2 + 1
	else:
		p = p // 2
	print('{:.4f}'.format(round(tot * (p - t) / p, 4)))


for i in range(int(input())):
	n = int(input())
	s = n * (n + 1) / 2
	l = list(map(int, input().split()))[1:]
	t = int(input())
	for x in l:
		s -= x
	n = (n + 1) // 2
	ans = (n - t) / n * s
	print('%.4f' % ans)


t = int(input())
for _ in range(t):
	pages = int(input())
	pages_sum = pages * (pages + 1) // 2
	missing_page_numbers = [int(x) for x in input().split()][1:]
	pages_sum -= sum(missing_page_numbers)
	if pages % 2 == 1:
		pages += 1
	missing_leaves = int(input())
	expected_sum = pages_sum - pages_sum * 2 * missing_leaves / pages
	print('{0:.4f}'.format(expected_sum))