Everybody loves magic, especially magicians who compete for glory on the Byteland Magic Tournament. Magician Cyael is one such magician.
Cyael has been having some issues with her last performances and today she’ll have to perform for an audience of some judges, who will change her tournament ranking, possibly increasing it. As she is a great magician she managed to gather a description of the fixed judges’ disposition on the room (which is represented as an N × N square matrix), such that she knows in advance the fixed points each judge will provide. She also knows that the room is divided into several parallel corridors, such that we will denote the j-th cell on corridor i, as [i][j]. Note that some judges can award Cyael, zero points or negative points, as they are never pleased with her performance. There is just one judge at each cell of the matrix, except the cells [1][1] and [N][N].
To complete her evaluation, she must start on the top leftmost corner of the room (cell [1][1]), and finish on the bottom right corner (cell [N][N]), moving either to the cell directly in front of her on the same corridor (that is, moving from cell [r][c] to cell [r][c+1], where c+1 ≤ N) or to the cell in the next corridor directly in front of where she is (that is, moving from cell [r][c] to cell [r+1][c], where r+1 ≤ N). She will keep doing this until she reaches the end point of the room, i.e. last cell [N][N] on the last corridor. Cyael will be judged at all visited cells with a judge.

Cyael wants to maximize her average score at end of her performance. More specifically, if she passes K judges, each being on cell [i_{1}][j_{1}], cell [i_{2}][j_{2}], ..., cell [i_{K}][j_{K}] respectively, then she wants to maximize (S[i_{1}][j_{1}] + S[i_{2}][j_{2}] + ... + S[i_{K}][j_{K}]) / K, where S[i][j] denotes the points that the judge will give her on the cell [i][j].
Help her determine the best path she has to follow in order to maximize her average points.

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

The first line contains a single integer T denoting the number of test cases. The description for T test cases follows. For each test case, the first line contains a single integer N. Each of the next N lines contains N space-separated integers.
The j-th integer S[i][j] in i-th line denotes the points awarded by the judge at cell [i][j].
Note that the cells [1][1] and [N][N] have no judges, so S[1][1] and S[N][N] will be 0.

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

For each test case, if the maximum possible average points Cyael can obtain is negative, output a single line containing "Bad Judges" (quotes for clarity). Otherwise, output the maximum possible average points. The answer will be considered correct if it has an absolute error no more than  10^{-6}.

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

1 ≤ T ≤ 20
2 ≤ N ≤ 100
-2500 ≤ S[i][j] ≤ 2500
S[1][1] = S[N][N] = 0

Your code will be judged against several input files. 

------ Example ------ 

----- Sample Input 1 ------ 
2
2
0 -4
8 0
2
0 -45
-3  0
----- Sample Output 1 ------ 
8.000000
Bad Judges
----- explanation 1 ------ 
Test case $1$: An optimal path for Cyael would be $(1,1)\rightarrow (2,1)\rightarrow (2,2)$. This way Cyael faces $1$ judge and gets a total score of $8$. Thus, the average score is $\frac{8}{1} = 8$.

Test case $2$: No matter what path Cyael chooses, the final score would be less than $0$.

Source: codechef | Difficulty: MEDIUM
Tags: Dynamic programming

Data structures


Solutions:
import math
import sys
import string
t = int(input())
while t:
	n = int(input())
	arr = [0] * n
	arr[0] = [int(x) for x in input().split()]
	for i in range(1, n):
		arr[0][i] += arr[0][i - 1]
	for i in range(1, n):
		arr[i] = [int(x) for x in input().split()]
		arr[i][0] += arr[i - 1][0]
		for j in range(1, n):
			arr[i][j] += max(arr[i][j - 1], arr[i - 1][j])
	if arr[n - 1][n - 1] < 0:
		print('Bad Judges')
	else:
		print('%.6f' % (arr[n - 1][n - 1] / (2 * n - 3)))
	t -= 1


t = int(input())
for _ in range(t):
	n = int(input())
	arr = []
	for _ in range(n):
		arr.append(list(map(int, input().split())))
	total_judge = 2 * n - 3
	for i in range(n):
		for j in range(n):
			if i == 0 and j == 0:
				pass
			elif i == 0:
				arr[i][j] += arr[i][j - 1]
			elif j == 0:
				arr[i][j] += arr[i - 1][j]
			else:
				arr[i][j] += max(arr[i - 1][j], arr[i][j - 1])
	if arr[-1][-1] < 0:
		print('Bad Judges')
	else:
		ans = arr[-1][-1] / total_judge
		print('{:.6f}'.format(ans))


t = int(input())
for _ in range(t):
	n = int(input())
	a = []
	for i in range(n):
		a.append(list(map(int, input().split())))
	ans = [[0] * n for i in range(n)]
	for i in range(1, n):
		ans[i][0] = ans[i - 1][0] + a[i][0]
		ans[0][i] = ans[0][i - 1] + a[0][i]
	for i in range(1, n):
		for j in range(1, n):
			ans[i][j] = a[i][j] + max(ans[i - 1][j], ans[i][j - 1])
	m = ans[n - 1][n - 1]
	tot = 2 * (n - 1) - 1
	print('{:.6f}'.format(m / tot) if m >= 0 else 'Bad Judges')


for t in range(int(input())):
	n = int(input())
	a = []
	for i in range(n):
		a.append(list(map(int, input().split())))
	dp = []
	for i in range(n):
		dp.append([])
	for i in range(n):
		for j in range(n):
			dp[i].append(0)
	dp[0][0] = 0
	for j in range(1, n):
		dp[0][j] = dp[0][j - 1] + a[0][j]
	for i in range(1, n):
		dp[i][0] = dp[i - 1][0] + a[i][0]
	for i in range(1, n):
		for j in range(1, n):
			dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + a[i][j]
	if dp[n - 1][n - 1] < 0:
		print('Bad Judges')
	else:
		x = n - 2
		x *= 2
		x += 1
		print('%.6f' % (dp[n - 1][n - 1] / x))


t = int(input())
for z in range(t):
	size = int(input())
	array = []
	for i in range(size):
		array.append(list(map(int, input().split())))
	for i in range(1, size):
		array[i][0] = int(array[i - 1][0]) + int(array[i][0])
	for i in range(1, size):
		array[0][i] = int(array[0][i - 1]) + int(array[0][i])
	for i in range(1, size):
		for j in range(1, size):
			array[i][j] = max(array[i - 1][j], array[i][j - 1]) + array[i][j]
	value = array[size - 1][size - 1] / (2 * size - 3)
	if value < 0:
		print('Bad Judges')
	else:
		print('%.6f' % value)


from itertools import islice

def calculate_rankings(judges):
	judges = [[-10 ** 6] * len(judges[0])] + judges
	judges = [[-10 ** 6] + row for row in judges]
	judges[0][1] = 0
	for (row_i, row) in islice(enumerate(judges), 1, None):
		for (cell_i, cell) in islice(enumerate(row), 1, None):
			judges[row_i][cell_i] += max(row[cell_i - 1], judges[row_i - 1][cell_i])
	return judges[-1][-1] / (2 * len(judges) - 5)
for _ in range(int(input())):
	n = int(input())
	judges = [[int(j) for j in input().split()] for _ in range(n)]
	ranking = calculate_rankings(judges)
	print('{:.6f}'.format(ranking) if ranking >= 0 else 'Bad Judges')


tn = int(input())
for _ in range(tn):
	n = int(input())
	ar = [list(map(int, input().split())) for _ in range(n)]
	dp = [[0 for _ in range(n + 1)] for _ in range(n + 1)]
	for i in range(1, n + 1):
		dp[0][i] = dp[i][0] = -1000000000
	for i in range(n):
		for j in range(n):
			if i == 0 and j == 0:
				dp[i + 1][j + 1] = ar[i][j]
				continue
			dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j]) + ar[i][j]
	sm = dp[-1][-1] / (2 * n - 3)
	if sm >= 0:
		print('{:.6f}'.format(sm))
	else:
		print('Bad Judges')


import sys

def trunc(f, n):
	return ('%.*f' % (n + 1, f))[:-1]
T = int(input())
while T > 0:
	N = int(input())
	arr = []
	for i in range(N):
		row = input().split()
		arr.append([])
		for inp in row:
			arr[i].append(int(inp))
	greed = [[0]]
	for i in range(1, N):
		greed.append([])
		greed[0].append(greed[0][i - 1] + arr[0][i])
		greed[i].append(greed[i - 1][0] + arr[i][0])
	for row in range(1, N):
		for col in range(1, N):
			possibility1 = greed[row - 1][col] + arr[row][col]
			possibility2 = greed[row][col - 1] + arr[row][col]
			finalResult = possibility1 if possibility1 > possibility2 else possibility2
			greed[row].append(finalResult)
	finalAnswer = float(greed[N - 1][N - 1])
	if finalAnswer >= 0:
		print('%s' % trunc(float(greed[N - 1][N - 1]) / (N + N - 3), 6))
	else:
		print('Bad Judges')
	T -= 1