little-jhool-and-his-addiction-2-4

Little Jhool is an addict. No, unlike the usual drug addicts, he's an addict of the good kind: the shopping addict. Some of his friends also call him a shopaholic, though he tries his level best to deny the title given to him by his friends. Now, he has some favorite websites as we already have seen in another question from where he always likes to buy things.

Anyway. As we already know, girls are crazy for Jhool and would do anything to be with him. It's no different this time. Little Jhool has n girlfriends, and every one of them wants to go e-shopping with him. Every single girl has a list with her which has Xi number of items to be bought. Jhool himself has n different lists to go shopping with every girlfriend - each list having some specific number of things to be bought. There are (n+n=2n) number of lists. So, the number of lists is always going to be even.

Now, Jhool does NOT want to upset his girlfriends! (Obviously!) So, he comes up with a devious plan to save the trouble. What he does is this: 
He takes all the n lists of items his girlfriends need to purchase, and his n lists and mixes all of them up and randomly gives everyone a list.
Now, no one can recognize their original list. Since the objective was spending time with each other, no one even cares. 
Consider the scenario that it takes one unit of time to get one item from any list. 
Now, if Little Jhool picks up a list with 12 items, for instance and pairs himself with a girl with 8 items: the total amount they'll spend together would be: (12 + 8 = 20 units of time!)

If a girl gets to spend more time with Jhool, she'll be happy, and the ones who wouldn't get much time would obviously be pissed. And Jhool doesn't want that to happen. So, he wants to pair up all the lists in such a way that the difference between the girl he's going to spend the maximum time with, and the girl he's going to spend the minimum time with is minimized!

We are also given a constant factor, k, if the minimum value is greater than this constant, his girlfriends would leave him, figuring out the bluff. If k would be equal to the minimum value, he would be just saved. And if it would be less, he would remain the magnet he is!

PS: We apologize on behalf of Little Jhool. We know that he has a bad habit of landing himself in a fix all the time. Just help him this one last time, come on!

Input format: 
The first line contains the number of test cases. The first line of the test cases contains two integers: 2n and k, which is followed by a vector representing all the 2n lists.

Output format: 
Print the minimum difference possible by pairing different lists. Also, print:  
 -  No more girlfriends! when ans > k.  
 -  Lucky chap! when ans == k.  
 -  Chick magnet Jhool! when ans < k.    

Constraints: 
1 ≤ Test Cases ≤ 50  
2 ≤ 2n ≤ 10^6    - No. of lists.  
1 ≤ Xi ≤ 10^6 - No. of items in a list.  
0 ≤ k ≤ 10^6

SAMPLE INPUT
3
2 1
4 2
6 4
1 6 6 7 1 8
4 0
2 6 4 3

SAMPLE OUTPUT
0
Chick magnet Jhool!
4
Lucky chap!
1
No more girlfriends!

Explanation

In the first case, since there will be only one pair, the minimum would be 0, which is less than the value of k. In the second test case, the value of k == 4, minimum value would be: [(8+1), (7+1), (6+6)] so, 12-8 == 4 which is equal to k. In the third case, k is greater than the answer, which is 1. [(6+2), (4+3)] -> [8-7] -> 1.

Difficulty: EASY
Tags: Sorting

Greedy algorithms
Skill types: Sorting

Greedy algorithms

Starter code:

Solutions:
for t in range(int(eval(input()))):
	n,k=list(map(int,input().split()))
	l=list(map(int,input().split()))
	nl=[]
	tt=0
	#print n,k
	l.sort()
	#print l
	if n<=2:
		tt=0
	else:
		if len(l)%2==0:
			i=0
			j=len(l)-1
			while i<j:
				nl.append(l[i]+l[j])
				i+=1
				j-=1 
		tt= max(nl)-min(nl)
	print(tt)
	if tt==k:
		print("Lucky chap!")
	elif tt<k:
		print("Chick magnet Jhool!")
	else:
		print("No more girlfriends!")
			
			
			
	
	
	


t = int(input())
while t:
	t = t - 1
	n,k = list(map(int, input().split()))
	li = list(map(int, input().split()))
	li.sort()
	minp = maxp = li[-1] + li[0]
	i = 0
	while i < n/2:
		s = li[i] + li[n-i-1]
		if s > maxp:
			maxp = s
		elif s < minp:
			minp = s
		i = i + 1
	ans = maxp-minp	
	print(ans)
	if ans > k:
		print("No more girlfriends!")
	elif ans == k:
		print("Lucky chap!")
	else:
		print("Chick magnet Jhool!")
		


from operator import add
t=eval(input())
while t!=0:
	input1=input().split()
	n=int(input1[0])
	k=int(input1[1])
	lists=list(map(int,input().split()))
	n=n/2
	lists.sort()
	list1=lists[0:n]
	list2=lists[n:2*n]
	list2.reverse()
	lists=list(map(add,list1,list2))
	min_val=max(lists)-min(lists)
	print(min_val)
	if min_val>k:
		print("No more girlfriends!")
	elif min_val==k:
		print("Lucky chap!")
	else:
		print("Chick magnet Jhool!")
	t=t-1


for i in range(eval(input())):
	n, k = list(map(int, input().split()))
	lst = sorted(list(map(int, input().split())))

	mx = -1
	mn = 10 ** 18

	for i in range(n // 2):
		v = lst[i] + lst[-i - 1]
		mx = max(v, mx)
		mn = min(v, mn)

	dif = mx - mn

	print(dif)
	if dif > k:
		print('No more girlfriends!')
	elif dif == k:
		print('Lucky chap!')
	else:
		print('Chick magnet Jhool!')


t = int(input())
for i in range(t):
	(n, k) = list(map(int, input().strip().split()))
	a = list(map(int, input().strip().split()))
	#print(a)
	a.sort()
	mini = maxi = a[0] + a[len(a)-1]
	for index in  range(1, len(a) // 2):
		left = a[index]
		right = a[n-index-1]
		summ = left + right
		if summ > maxi:
			maxi = summ
		if summ < mini:
			mini = summ
	#print(maxi)
	dif = maxi - mini
	print(dif)
	if dif == k:
		print("Lucky chap!")
	elif dif > k:
		print("No more girlfriends!")
	else:
		print("Chick magnet Jhool!")


t=int(input())
for j in range(t):
	n= input()
	s = list(n.split())
	N=[]
	for x in s:
		if x != ' ':
			N.append(int(x))
	a= input()
	ax = list(a.split())
	b=[]
	for x in ax:
		if x != ' ':
			b.append(int(x))
	 
	n = N[0]
	c=sorted(b)
	n=n/2
	i=0
	for x in range(1, n+1):
		b[i]=c[n-1+x]
		b[i+1]=c[n-x]
		i=i+2 
	i=0
	max= 0
	min = 100000
	for x in range (0, n):
		t=b[i]+b[i+1]
		if t > max:
			max=t
		if t<min:
			min= t
		i=i+2
	print(max-min)
	if max- min > N[1]:
		print("No more girlfriends!")
	elif max-min < N[1]:
		print("Chick magnet Jhool!")
	else:
		print("Lucky chap!")
	
	


'''
# 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())
while(T!=0):
	N,k=list(map(int,input().strip().split()))
	arr = list(map(int,input().strip().split()))

	arr.sort()
	best = 0
	#print arr
	pairs = []
	if len(arr) == 2:
		best =0
	
	else:
		for i in range(0,N/2):
			pairs.append(arr[i]+arr[N-i-1])	
		#print pairs
		best = max(pairs)-min(pairs)
	
	print(best)
	if best > k:
		print("No more girlfriends!")
	elif best == k:
		print("Lucky chap!")
	else:
		print("Chick magnet Jhool!")
	T=T-1


for test in range(eval(input())):
	a=list(int(i) for i in input().split())
	n=a[0]
	k=a[1]
	b=sorted(list(int(i) for i in input().split()))
	lista=list(b[m]+b[n-m-1] for m in range(n//2))
	Max=max(lista)
	Min=min(lista)
	diff=Max-Min
	print(diff)
	if diff>k:
		print("No more girlfriends!")
	elif diff==k:
		print("Lucky chap!")
	elif diff<k:
		print("Chick magnet Jhool!")


def check(l, n, k):
	i = 0
	j = n-1

	b = []
	for _ in range(int(n/2)):
		b.append(l[i] + l[j])
		i=i+1
		j=j-1

	ans = max(b) - min(b)

	print(ans)

	if ans > k:
		print('No more girlfriends!')

	elif ans == k:
		print('Lucky chap!')

	else:
		print('Chick magnet Jhool!')
	
if __name__=='__main__':
	T = int(eval(input()))
	
	for i in range(T):
		n, k = list(map(int, input().split()))
		l = sorted(list(map(int, input().split())))
		
		check(l, n, k)


t=eval(input())
for _ in range(t):
	tn,k=list(map(int,input().split()))
	l=list(map(int,input().split()))
	l.sort()
	mi=10**14
	ma=0
	for i in range(len(l)/2):
		x=l[i]+l[len(l)-i-1]
		if x<mi: mi=x
		if x>ma: ma=x
	print(ma-mi)
	if ma-mi<k: print("Chick magnet Jhool!")
	if ma-mi==k: print("Lucky chap!")
	if ma-mi>k: print("No more girlfriends!") 


def solve(xs, k):
	xs.sort()
	pairs = [x + y for x, y in zip(xs[:len(xs) / 2], xs[len(xs) / 2:][::-1])]
	diff = max(pairs) - min(pairs)
	if diff < k: res = "Chick magnet Jhool!"
	elif diff == k: res = "Lucky chap!"
	else: res = "No more girlfriends!"
	return '{}\n{}'.format(diff, res)

if __name__ == '__main__':
	for _ in range(int(input())):
		_, k = list(map(int, input().split()))
		xs = list(map(int, input().split()))
		print(solve(xs, k))


T = int(input())
for m in range(T):
	tn,k = [int(x) for x in input().split()]
	shop_list = [int(x) for x in input().split()]
	shop_list.sort()
	n= tn//2
	l1 =[]+ shop_list[0:n]
	l2 =[]+ shop_list[n:]
	l2.sort(reverse=True)
	sum_l =[]
	for i in range(n):
		sum_l.append(l1[i]+l2[i])

	ans = max(sum_l)-min(sum_l)
	print(ans)
	
	if ans > k:
	
		print("No more girlfriends!")

	if ans == k:
		print("Lucky chap!")

	if ans < k:
		print("Chick magnet Jhool!")
		
		
		
	
	


for _ in range(eval(input())):
	n,m=list(map(int,input().split()))
	a=list(map(int,input().split()))
	a.sort()
	c,k=1000000,0
	d=[a[x]+a[n-1-x] for x in range(n/2)]
	d.sort()
	k=d[n/2-1]-d[0]
	if k>m:
		print(k)
		print("No more girlfriends!")
	elif k==m:
		print(k)
		print("Lucky chap!")
	else :
		print(k)
		print("Chick magnet Jhool!")
			


t=eval(input())
for _ in range(t):
	n,k=list(map(int, input().split()))
	l = [int(i) for i in input().split()]
	l.sort()
	maxi,mini=0,1000000
	for i in range(n/2):
		maxi=max(maxi,l[i]+l[n-i-1])
		mini=min(mini,l[i]+l[n-i-1])
	print(maxi-mini)
	if maxi-mini>k: 
		print("No more girlfriends!")
	elif abs(maxi-mini)<k:
		print("Chick magnet Jhool!")
	else:
		print("Lucky chap!")
		


t=eval(input())
for _ in range(t):
	tn,k=list(map(int,input().split()))
	l=list(map(int,input().split()))
	l.sort()
	mi=10**14
	ma=0
	for i in range(len(l)/2):
		x=l[i]+l[len(l)-i-1]
		if x<mi: mi=x
		if x>ma: ma=x
	print(ma-mi)
	if ma-mi<k: print("Chick magnet Jhool!")
	if ma-mi==k: print("Lucky chap!")
	if ma-mi>k: print("No more girlfriends!")


# Enter your code here. Read input from STDIN. Print output to STDOUT
for i in range(0,int(input())):
	n2 = list(map(int, input().split())) 
	l = list(map(int, input().split()))
	l.sort()
	max = l[0]+l[n2[0]-1]
	min = l[0]+l[n2[0]-1]
	m = n2[0]/2 
	for j in range(1,m):
		m = l[j] + l[n2[0]-j-1]
		if m > max:
			max = m
		if m < min :
			min = m
	
	print(max-min)        
	if max-min > n2[1]:
		print("No more girlfriends!")
	elif max-min==n2[1]:
		print("Lucky Chap!")
	else:
		print("Chick magnet Jhool!")


for _ in range(int(input())):
	n,k=list(map(int,input().split()));
	a=list(map(int,input().split()));	a.sort();	i,j,min_v,max_v=0,len(a)-1,999999,0;
	while i<n/2:
		min_v=min(min_v,a[i]+a[j]);
		max_v=max(max_v,a[i]+a[j]);
		i+=1;	j-=1;
	if max_v-min_v==k:
		print(max_v-min_v)
		print("Lucky chap!")
	elif max_v-min_v<k:
		print(max_v-min_v)
		print("Chick magnet Jhool!")
	else:
		print(max_v-min_v)
		print("No more girlfriends!")


t = int(input())
while t:
	t = t - 1
	n,k = list(map(int, input().split()))
	li = list(map(int, input().split()))
	li.sort()
	# import pdb; pdb.set_trace()
	minp = li[-1] + li[0]
	maxp = li[-1] + li[0]
	i = 0
	j = n-1
	while i < n/2:
		s = li[i] + li[j]
		if s > maxp:
			maxp = s
		elif s < minp:
			minp = s
		i = i + 1
		j = j - 1
	print(maxp-minp)	
	if maxp - minp > k:
		print("No more girlfriends!")
	elif maxp - minp == k:
		print("Lucky chap!")
	else:
		print("Chick magnet Jhool!")


noOfTestCases = int(input())

def  minimumPossDiff(items, k):
	citems = []
	for i in items:
		citems.append(int(i))	
	citems.sort();
	
	times = []
	traversalPointer = 0
	traversalEnd = len(citems) / 2 - 1
	listLen = len(citems)
	
	while(traversalPointer <= traversalEnd):
		times.append(citems[traversalPointer] + citems[listLen - traversalPointer -1 ] )
		traversalPointer += 1
	
	mx = max(times)
	mn = min(times)
	diff = mx - mn
	print(diff)
	
	if(diff > k):
		print('No more girlfriends!')
	elif (diff == k ):
		print('Lucky chap!')
	else:
		print('Chick magnet Jhool!')
		

for i in range(1, noOfTestCases + 1):
	count, k = input().split(" ")
	k = int(k)
	items = input().split(" ")
	minimumPossDiff(items, k)
	
	


T = int(input())
for _ in range(T):
	l = [int(e) for e in input().split()]
	twon,k = int(l[0]),int(l[1])
	lis = [int(e) for e in input().split()]
	if twon == 2:
		print(0)
		if k == 0:
			print("Lucky chap!")
		else:
			print("Chick magnet Jhool!")
	else:
		fhalf =sorted(lis)
		minm = fhalf[0]+fhalf[twon-1]
		maxm = fhalf[0]+fhalf[twon-1]
		for i in range(twon/2):
			minm = min(minm,fhalf[i]+fhalf[twon-1-i])
			maxm = max(maxm,fhalf[i]+fhalf[twon-1-i])
			r = maxm - minm
		print(r)
		if r > k:
			print("No more girlfriends!")
		elif r == k:
			print("Lucky chap!")
		else:
			print("Chick magnet Jhool!")
			


test = eval(input())
while test:
	test-=1
	n,k = list(map(int,input().split()))
	arr = list(map(int,input().split()))
	arr.sort()
	sumo = 0
	new = []
	i = 0
	j = n-1
	while i<j:
		new.append(arr[i]+arr[j])
		i+=1
		j-=1
	val = max(new)-min(new)
	if val>k:
		print(val)
		print("No more girlfriends!")
	elif val==k:
		print(val)
		print("Lucky chap!")
	else:
		print(val)
		print("Chick magnet Jhool!")