Read problems statements in Mandarin Chinese here 

------ Problem Statement ------ 

Little Elephant from Zoo of Lviv likes bamboo very much. He currently has n stems of bamboo, H_{i} - height of i-th stem of bamboo (0-based numeration). 

Today inspector Andrii from World Bamboo Association is visiting the plantation. He doesn't like current situation. He wants the height of i-th stem to be D_{i}, for each i from 0 to n-1, inclusive.

Little Elephant is going to buy some special substance. One bottle of such substance he can use to single stem of bamboo. After using substance for stem i, the height of i-th stem is decrased by 1 and the height of j-th stem is increased by 1 for each j not equal to i. Note that it is possible for some of the stems to have negative height, but after all transformations all stems should have positive height.

Substance is very expensive. Help Little Elephant and find the minimal number of bottles of substance required for changing current plantation to one that inspector wants. If it's impossible, print -1.

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

First line contain single integer T - the number of test cases. T test cases follow. First line of each test case contains single integer n - the number of stems in the plantation. Second line contains n integers separated by single space - starting plantation. Next line of each test case contains n integers - plantation that inspector Andrii requires.

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

In T lines print T integers - the answers for the corresponding test cases.

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

1 ≤ T ≤ 50

1 ≤ n ≤ 50

1 ≤ H_{i}, D_{i} ≤ 50

----- Sample Input 1 ------ 
3
1
1
2
2
1 2
2 1
3
3 2 2
4 5 3
----- Sample Output 1 ------ 
-1
1
5

Difficulty: MEDIUM_HARD
Tags: Mathematics

Starter code:

Solutions:
class Solu(object):

	def solve(self, N, H, D):
		if N == 1:
			return max(H[0] - D[0], -1)
		elif N == 2:
			a = H[0] - D[0]
			b = H[1] - D[1]
			if a == 0 and b == 0:
				return 0
			elif a != b and abs(a) == abs(b):
				return abs(a)
			else:
				return -1
		else:
			d = sum(D)
			h = sum(H)
			if d < h:
				return -1
			r = (d - h) % (N - 2)
			if r != 0:
				return -1
			s = (d - h) / (N - 2)
			for i in range(N):
				r = (s + H[i] - D[i]) % 2
				if r != 0:
					return -1
				xi = 0.5 * (s + H[i] - D[i])
				if xi < 0:
					return -1
			return int(s)
sol = Solu()
T = int(input())
for _ in range(T):
	n = int(input())
	H = input().split(' ')
	D = input().split(' ')
	for i in range(0, len(H)):
		H[i] = int(H[i])
		D[i] = int(D[i])
	res = sol.solve(n, H, D)
	print(res)


def one_test():
	n = int(input())
	a = map(int, input().split())
	b = map(int, input().split())
	d = [y - x for (x, y) in zip(a, b)]
	sum_d = sum(d)
	if n == 1:
		return -d[0] if d[0] <= 0 else -1
	if n == 2:
		return abs(d[0]) if sum_d == 0 else -1
	if sum_d % (n - 2):
		return -1
	sum_d //= n - 2
	return sum_d if all((sum_d >= x and (sum_d - x) % 2 == 0 for x in d)) else -1
t = int(input())
for i in range(t):
	print(one_test())


for _ in range(int(input())):
	n = int(input())
	li = list(map(int, input().split()))
	di = list(map(int, input().split()))
	if n == 1:
		if li[0] >= di[0]:
			print(li[0] - di[0])
		else:
			print(-1)
	elif n == 2:
		if sum(li) == sum(di):
			print(abs(li[0] - di[0]))
		else:
			print(-1)
	else:
		dif = sum(di) - sum(li)
		ans = dif // (n - 2)
		if dif < 0 or dif % (n - 2) != 0:
			print(-1)
		else:
			for i in range(n):
				x = ans + li[i] - di[i]
				if x < 0 or x % 2 != 0:
					ans = -1
					break
			print(ans)


def ALL_MOD_2(L):
	x = L[0] % 2
	for item in L:
		if item % 2 != x:
			return False
	return True
import sys
T = int(sys.stdin.readline())
Ans = ''
for t in range(T):
	n = int(sys.stdin.readline())
	H = list(map(int, sys.stdin.readline().split()))
	D = list(map(int, sys.stdin.readline().split()))
	for i in range(n):
		D[i] -= H[i]
	if D.count(0) == n:
		Ans += '0\n'
		continue
	if n == 1 and D[0] > 0:
		Ans += '-1\n'
		continue
	if n == 1 and D[0] < 0:
		Ans += str(-D[0]) + '\n'
		continue
	if ALL_MOD_2(D) == False:
		Ans += '-1\n'
		continue
	start = max(max(D), 1)
	if D[0] % 2 != start % 2:
		start + 1
	for s in range(start, 5000, 2):
		F = []
		A = []
		s_F = 0
		s_A = 0
		for item in D:
			A.append((s + item) // 2)
			F.append(s - A[-1])
			s_F += F[-1]
			s_A += A[-1]
		case = True
		if s_F != s:
			case = False
			continue
		for i in range(n):
			if A[i] != s_F - F[i]:
				case = False
				break
		if case:
			Ans += str(s) + '\n'
			break
	if case == False:
		Ans += '-1\n'
		continue
sys.stdout.write(Ans)


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	d = list(map(int, input().split()))
	if n == 1:
		if l[0] >= d[0]:
			print(l[0] - d[0])
		else:
			print(-1)
	elif n == 2:
		if sum(l) == sum(d):
			print(abs(l[0] - d[0]))
		else:
			print(-1)
	else:
		f = sum(d) - sum(l)
		ans = f // (n - 2)
		if f < 0 or f % (n - 2) != 0:
			print(-1)
		else:
			for k in range(n):
				x = ans + l[k] - d[k]
				if x < 0 or x % 2 != 0:
					ans = -1
					break
			print(ans)


class Main:

	def __init__(self):
		iterable = self.__standard()
		self.__solution(iterable)

	def __solution(self, iterable):
		(cases,) = map(int, next(iterable).split())
		for _test in range(cases):
			(count,) = map(int, next(iterable).split())
			items0 = list(map(int, next(iterable).split()))
			items = list(map(int, next(iterable).split()))
			total0 = sum(items0)
			total = sum(items)
			delta = total - total0
			step = count - 2
			if not step:
				if not delta:
					print(abs(items[0] - items0[0]))
				else:
					print(-1)
				continue
			if delta % step:
				print(-1)
				continue
			rounds = delta // step
			if rounds < 0:
				print(-1)
				continue
			accumulated = 0
			for (element0, element) in zip(items0, items):
				additional = rounds + element0 - element
				if additional < 0 or additional & 1:
					print(-1)
					break
				accumulated += additional >> 1
			else:
				if accumulated == rounds:
					print(rounds)
				else:
					print(-1)

	def __test(self):
		yield '3'
		yield '1'
		yield '1'
		yield '2'
		yield '2'
		yield '1 2'
		yield '2 1'
		yield '3'
		yield '3 2 2'
		yield '4 5 3'

	def __standard(self):
		try:
			while True:
				yield input()
		except EOFError:
			pass
Main()