add-subtract

Chandan is back with his array to blow your mind. As usual Chandan has an array consisting of N integers .He allows you to perform 2 kinds of operation on his array.

Type 1 : Increment any integer of the array by 1.

Type 2 : Decrement any integer of the array by 1.

You can perform these operation as many times as you want on his array.

Each  operation of Type 1 costs 3 while each operation of Type 2 costs 5.

Now Chandan wants to have K equal elements in his array.So he asks you to tell him the minimum cost required in obtaining K equal elements in his array.

Input:

The first line contains T indicating test cases.Second line contains 2 integers N indicating the number of elements in his array and K.

Third line contains N space separated integers denoting Chandan array.

Output:

The minimum cost required to get K equal elements.

Constraints :

1 ≤ T ≤ 100

1 ≤ K ≤ N ≤100

1 ≤ A[i] ≤100

SAMPLE INPUT
1
5 3
9 4 9 7 4 

SAMPLE OUTPUT
6

Explanation

We can convert 7 to 9 to get three 9. The cost of this conversion will be 6.

Source: hackerearth | Difficulty: EASY
Tags: Greedy algorithms

Sorting

Complete search


Solutions:
t = eval(input())
for t in range(t):
	n,k = list(map(int,input().split()))
	arr = list(map(int,input().split()))
	new_arr = sorted(set(arr))
	new_len = len(new_arr)
	count_arr = []
	cost_arr = [[] for x in range(105)]
	cost_arr_min=[]
	def calculate_cost(i,arr_sent):
		for j in arr_sent:
			r = arr.count(j)
			if i>j:
				diff = i-j
				n = [diff*3]*r
				cost_arr[i]+=n
			else:
				diff= j-i
				n = [diff*5]*r
				cost_arr[i]+=n

	for i in range(new_len):
		j = arr.count(new_arr[i])
		count_arr.append(j)
		j_value = k - j
		j_list = [x for x in new_arr if x!=new_arr[i]]
		calculate_cost(new_arr[i],j_list)
		cost = 0
		while j_value>0:
			cost_arr[new_arr[i]].sort(reverse=True)
			cost += cost_arr[new_arr[i]].pop()
			j_value -= 1
		cost_arr_min.append(cost)	
	print(min(cost_arr_min))





t = eval(input())
for t in range(t):
	n,k = list(map(int,input().split()))
	a = list(map(int,input().split()))
	b = sorted(set(a))
	l = len(b)
	m = max(b)
	c = []
	d = [[] for x in range(105)]
	cost_min=[]
	def calculate(i,arr):
		# print "arr=",arr
		for j in arr:
			r = a.count(j)
			if i>j:
				diff = i-j
				n = [diff*3]*r
				# print "for {0} diff={1}".format(j,diff)
				d[i]+=n
				# print d[i]
			else:
				diff= j-i
				n = [diff*5]*r
				# print "for {0} diff={1}".format(j,diff)
				d[i]+=n
				# print d[i]

	for i in range(l):
		j=a.count(b[i])
		c.append(j)
		j_k = k-j
		j_k_l=[]
		j_l = [x for x in b if x!=b[i]]
		calculate(b[i],j_l)

		x = 0
		while j_k>0:
			j_k -= 1
			d[b[i]].sort(reverse=True)
			# print "di==",d[b[i]]
			y = d[b[i]].pop()
			# print y
			x += y
		cost_min.append(x)	
	print(min(cost_min))





import sys

def findMinCost(Ai,index, K):
	minCost = 0
	cost = []
	for (idx,item) in enumerate(Ai):
		if idx != index:
			c = 0
			if item > Ai[index]:
				c = (item-Ai[index]) * 5
			else:
				c = (Ai[index]-item) * 3
			cost.append(c)
	for costs in sorted(cost):
		if K>0:
			minCost = minCost + costs
			K = K - 1
	return minCost

T = int(input())
for i in range(T):
	N,K = input().split()
	N = int(N)
	K = int(K)
	Ai = list(map(int,input().split()))
	minCost = sys.maxsize    
	for (index,item) in enumerate(Ai):
		tempCost = findMinCost(Ai,index, K-1)
		if tempCost < minCost:
			minCost = tempCost
	print(minCost)


import sys
 
T  = int(input())
while T > 0:
	N,K = list(map(int,input().split(" ")))
	A = list(map(int,input().split()))
	ans = sys.maxsize
	for i in range(1,101):
		cost = []
		for x in A:
			if i > x:
				cost.append((i-x) * 3)
			else:
				cost.append((x-i) * 5)
 
		cost =sorted(cost)
		temp = sum(cost[0:K])
		
		ans = min(ans,temp)
	print(ans)
	T -= 1


#0 1 2 3 4 15 15 16 17 19
#  1 1 1 1 11  0  1  1  1
#  3 3 3 3 33  0  3  3  3
#5 5 5 5 55 0  5  5  5 
from copy import copy

for tc in range(eval(input())):
	N, K = list(map(int, input().split()))
	A = list(map(int, input().split()))
	cost = 10**6
	
	for a in range(1, 101):
		cp = []
		for item in A:
			if a > item: cp.append((a-item)*3)
			else: cp.append((item-a)*5)
#		print 
		cost = min(cost, sum(sorted(cp)[:K]))
		
	print(cost)


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

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
def chandan(x):
	n,k=x.split(' ')
	n,k=int(n),int(k)
	sub_ls=[]
	main_ls=list(map(int,input().split()))
	main_ls.sort()
	for i in range(n-k+1):
		ls=[]
		for j in range(k):
			ls.append(main_ls[i+j])
		sub_ls.append(ls)
	sub_ls.sort()
	ls_cost=cost(sub_ls,k) 
	print(ls_cost)
		
def cost(sub_ls,k):
	ls=sub_ls[0]
	cost=(abs(sum(ls[:1])-(len(ls[:1])*ls[0]))*3)+(abs(sum(ls[1:])-(len(ls[1:])*ls[0]))*5)
	for j in range(len(sub_ls)):
		ls=sub_ls[j]
		for i in range(0,k):
			cost=min(((abs(sum(ls[:i])-(len(ls[:i])*ls[i]))*3)+(abs(sum(ls[i+1:])-(len(ls[i+1:])*ls[i]))*5)),cost)
	return cost

for i in range(int(input())):
	chandan(input())
	


t=int(input())
n=[]
l=[]
for k in range(t):
	n.append(input())
	l.append(input())

def getmin(l):
	mn=-1
#	print l
	for i in l:
		cost=0
		for j in l:
			temp=i-j
			#print temp
			if(temp<0):
				temp=abs(temp)*5
			else:
				temp=abs(temp)*3
			cost+=temp
		#print cost
		if mn==-1 or mn>cost:
			mn=cost
	return mn
			

for k in range(t):
	arr = list(map(int,l[k].split()))
	size,subsize = list(map(int,n[k].split()))
	arr.sort()
	#print arr
	soln=[]
	for i in range(size-subsize+1):
		soln.append(getmin(arr[i:i+subsize]))
	#print soln
	print(min(soln))
	del soln
	


T = int(input())
for _ in range(T):
	N,K = (int(e) for e in input().split())
	lis = [int(e) for e in input().split()]
	sl = sorted(lis,reverse=True)
	minn=100000
	for i in range(len(sl)):
		a=i-1
		b=i+1
		countt=1
		costt=0
		while countt!=K:
			if a>=0:
				costdec=(sl[a]-sl[i])*5
			else:
				costdec=100000
			if b<len(sl):
				costinc=(sl[i]-sl[b])*3
			else:
				costinc=100000
			if costinc<costdec:
				b+=1
				costt+=costinc
			else:
				a-=1
				costt+=costdec
			countt+=1
			costt
		minn=min(minn,costt)
	print(minn)		


tc = int(input())
while(tc > 0):
	tc -= 1
	num_list = []
	N,K = list(map(int,input().split()))
	num_list = list(map(int,input().split()))
	num = 0
	
	tsum = 0
	sum_list = []
	for i in range(N):
		num_list.sort()
		num = num_list[i]
		#print num
		cost = []
		for x in num_list:
			
			scost = 0
			#print x 
			if num >= x:
				#print x
				scost = (num - x) * 3
				cost.append(scost)
				#print scost
			else:
				
				scost = (x - num) * 5
				cost.append(scost)
				#print scost
		
		cost.sort()
		#print cost
		tsum = sum(cost[:K])
		#print tsum
		sum_list.append(tsum)
		
	print(min(sum_list))
		
			
		#print tsum