utkarsh-and-distributing-books-february-easy

Utkarsh's mother recently received N piles of books as a gift from someone. The i^th pile contains Bi books.

She neither wants to keep the voluminous books with herself nor she wants to throw them away.  So, she decided to distribute them to students of the nearby school. She decided to call K students to her home and ask one of her sons (Utkarsh or Saharsh) to distribute books.   

Also, she will get happy only if the following condition is satisfied: For every pile i there must be at least one student who receives more than one books from pile i.

She knows that Utkarsh is very lazy. So he will randomly pick a student and give him a book from any pile. Since he distributes randomly,  he might make her sad.  

On the other hand, Saharsh is smart and obedient so he will always find a way of distribution (if possible)  which will make her happy.  

You need to output 2 integers : The maximum value of K

When Utkarsh is asked to distribute the books. His mother must remain happy irrespective of the way of his distribution.  

When Saharsh is asked to distribute the books.

Input format:
The first line contains an integer T, denoting  the number of test cases.
The first line of each test case contains an integer N, denoting the number of piles.
The next line contains N integers, the array B.
Output format:
For each test case, print two space separated integers: The maximum value of K if Utkarsh distributes and the maximum value of K if Saharsh distributes the books.
Constraints:
1 ≤ T ≤ 10
1 ≤ N ≤ 1000  
2 ≤ Bi ≤ 1000

SAMPLE INPUT
1
2
5 5

SAMPLE OUTPUT
4 8

Explanation
When Utkarsh is distributing, 4 is the maximum value of K. If K = 5 then there is a chance that he can give the 5 books of the first pile to 5 different students. This might make his mother unhappy.
Saharsh can distribute in this way to have K = 8: (1,1)(2) (1)(2) (1)(2,2)(1)(2)

Source: hackerearth | Difficulty: EASY


Solutions:
t=eval(input())
while(t>0):
	n=eval(input())
	b=input()
	l=b.split()
	for x in range(0,len(l)):
		l[x]=int(l[x])
	a=min(l)
	s=0
	for x in range(0,len(l)):
		l[x]=l[x]-2
		s=s+l[x]
	stri='{} {}'.format(a-1,s+len(l))
	print(stri)
	t=t-1


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
#print 'Hello World!'

T =int(input())
for i in range(T):
	S=int(input())
	T=[int(x) for x in input().split()]
	U=min(T)-1
	Sa=sum(T)-S
	print(U,Sa)


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
T=int(input())
for j in range(0,T):
	sum_books=0
	n_piles=int(input())
	n_books=input().split()
	min_num=int(n_books[0])
	for i in range(0,n_piles):
		sum_books+=int(n_books[i])
		if int(n_books[i])<min_num:
			min_num=int(n_books[i])
	utk_k=min_num-1
	print(utk_k, end=' ')
	sah_k=sum_books-n_piles
	print(sah_k)



test = int(input())
while test:
	n = int(input())
	arr = list(map(int,input().split()))
	utkarsh = min(arr) - 1
	sum = 0
	for i in arr:
		sum += i-1
	print(utkarsh, end=' ')
	print(sum)
	test -= 1


t=eval(input())
for _ in range(t):
	n=eval(input())
	a=list(map(int,input().split()))
	ut=min(a)-1
	sr=n
	for i in a:
		sr+=(i-2)
	print(ut,sr)


tc = int(input())
while tc>0:
	tc = tc - 1
	n = int(input())
	l = list(map(int, input().split()))
	ans = 0
	for i in l:
		ans = ans + i-1
	print(min(l)-1,ans)


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
t=int(input())
for kk in range(t):
	n = int(input())
	xx = input()
	b = [int(j) for j in xx.split(' ') if j !='' ]
	b.sort()
	u = b[0] - 1
	s = 0
	for a in b:
		s+=a
	s = s-n
	print(u,s)


t = eval(input())
while t:
	n = eval(input())
	b = list(map(int,input().split()))
	print(min(b)-1, end=' ')
	print(sum(b)-n)
	t -=1


t = int(input().strip())
for i in range(0,t):
	n = int(input().strip())
	books = [int(i) for i in input().strip().split()]
	utkarsh = books[0] - 1
	sahrash = 0
	for pile in books:
		if pile > 1:
			sahrash += 1 +(pile-2)
		else:
			sahrash += 1
		utkarsh = min(utkarsh, pile-1)
	print(utkarsh, sahrash)


T = eval(input())
result = ''
for i in range(T):
	No_piles = eval(input())
	int_list = [int(x) for x in input().split()]
	result += str(min(int_list)-1)
	sum_1 = 0
	for i in int_list:
		sum_1 += (i-1)
	result += ' ' + str(sum_1) + '\n'
print(result)
		
	
		


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
T = int(input())
s = 0
r1 = list()
r2 = list()
for i in range(1, T+1):
	N = int(input())
	B = list()
	for x in input().split():
		B.append(int(x))
	for x in B:
		s += (x-1)
	r1.append(int(min(B) - 1))
	r2.append(int(s))
	s = 0
for i in range(0,T):
	print(r1[i], r2[i])


T=int(input())
B=[]
A=[]
for i in range(0,T):
	N=int(input())
	S=input()
	B=S.split()
	for i in range(0,N):
		a=int(B[i])
		A.append(a)
	m=min(A)
	U=m-1
	s=sum(A)-2*(N)
	K=s+N
	print(U,K)
	A=[]
	B=[]
	



'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
#print 'Hello World!'
t=int(input())
for kk in range(t):
	n = int(input())
	xx = input()
	b = [int(j) for j in xx.split(' ') if j !='' ]
	b.sort()
	u = b[0] - 1
	s = 0
	for a in b:
		s+=a
	s = s-n
	print(u,s)


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
#print 'Hello World!'
for m in range(int(input())):
	piles = int(input())
	bookCount = [int(i) for i in input().split(" ") if i!='']
	ukarsh = min(bookCount)-1
	sCount=0
	for i in range(len(bookCount)):
		sCount=sCount+(bookCount[i]-1)
	saharsh = sCount
	print(ukarsh, end=' ')
	print(saharsh)


for _ in range(int(input())):
	n = int(input())
	piles = [int(s) for s in input().split()]
	print(("{} {}".format(min(piles) - 1, sum(piles) - n)))


t=eval(input())
for _ in range(t):
	n=eval(input())
	a=list(map(int,input().split()))
	ut=min(a)-1
	sr=n
	for i in a:
		sr+=(i-2)
	print(ut,sr)


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
#print 'Hello World!'
for m in range(int(input())):
	piles = int(input())
	bookCount = [int(i) for i in input().split(" ") if i!='']
	utkarsh = min(bookCount)-1
	sCount=0
	for i in range(len(bookCount)):
		sCount=sCount+(bookCount[i]-1)
	saharsh = sCount
	print(utkarsh, end=' ')
	print(saharsh)