Marc loves cupcakes, but he also likes to stay fit. Each cupcake has a calorie count, and Marc can walk a distance to expend those calories.  If Marc has eaten $j$ cupcakes so far, after eating a cupcake with $\textbf{C}$ calories he must walk at least $2^j\times c$  miles to maintain his weight.

Example 

$calorie=[5,10,7]$   

If he eats the cupcakes in the order shown, the miles he will need to walk are $(2^0\times5)+(2^1\times10)+(2^2\times7)=5+20+28=53$.  This is not the minimum, though, so we need to test other orders of consumption.  In this case, our minimum miles is calculated as $(2^0\times10)+(2^1\times7)+(2^2\times5)=10+14+20=44$.

Given the individual calorie counts for each of the cupcakes, determine the minimum number of miles Marc must walk to maintain his weight. Note that he can eat the cupcakes in any order.  

Function Description  

Complete the marcsCakewalk function in the editor below.  

marcsCakewalk has the following parameter(s):  

int calorie[n]: the calorie counts for each cupcake   

Returns   

long: the minimum miles necessary

Input Format

The first line contains an integer $n$, the number of cupcakes in $calorie$. 

The second line contains $n$ space-separated integers, $\text{calorie}[i]$.

Constraints

$1\leq n\leq40$
$1\leq c[i]\leq1000$

Sample Input 0
3
1 3 2

Sample Output 0
11

Explanation 0

Let's say the number of miles Marc must walk to maintain his weight is $miles$. He can minimize $miles$ by eating the $n=3$ cupcakes in the following order: 

Eat the cupcake with $c_1=3$ calories, so $miles=0+(3\cdot2^0)=3$.
Eat the cupcake with $c_2=2$ calories, so $miles=3+(2\cdot2^1)=7$.
Eat the cupcake with $c_{0}=1$ calories, so $miles=7+(1\cdot2^2)=11$.

We then print the final value of $miles$, which is $\mbox{11}$, as our answer.

Sample Input 1
4
7 4 9 6

Sample Output 1
79

Explanation 1

$(2^0*9)+(2^1*7)+(2^2*6)+(2^3*4)=9+14+24+32=79$

Difficulty: EASY
Tags: Greedy algorithms
Skill types: Greedy algorithms

Starter code:

Solutions:
import sys
n = int(input().strip())
calories = list(map(int, input().strip().split(' ')))
calories.sort(reverse=True)
print(sum([2 ** j * calories[j] for j in range(n)]))


import sys
n = int(input().strip())
calories = list(map(int, input().strip().split(' ')))
calories.sort()
toplam = 0
count = 0
for kalori in calories[::-1]:
	toplam += kalori * 2 ** count
	count += 1
print(toplam)


import sys
n = int(input().strip())
calories = sorted(list(map(int, input().strip().split(' '))), reverse=True)
print(sum([calories[i] * 2 ** i for i in range(n)]))


input()
a = list(map(int, input().split()))
a.sort(reverse=True)
x = 0
y = 1
for i in a:
	x += y * i
	y <<= 1
print(x)


import sys
n = int(input().strip())
calories = list(map(int, input().strip().split(' ')))
calories.sort(reverse=True)
ans = 0
for x in range(0, n):
	ans = ans + 2 ** x * calories[x]
print(ans)


n = input()
x = list(map(int, input().split()))
x.sort()
erg = 0
for i in range(len(x)):
	erg += x[i] * 2 ** (len(x) - i - 1)
print(erg)


import sys
n = int(input().strip())
calories = list(map(int, input().strip().split(' ')))
total = 0
sort = sorted(calories)
j = 0
for c in sort[::-1]:
	total += 2 ** j * c
	j += 1
print(total)


import sys
n = int(input().strip())
calories = list(map(int, input().strip().split(' ')))
c = list(reversed(sorted(calories)))
s = 0
for i in range(len(c)):
	s += c[i] * 2 ** i
print(s)


n = input()
a = [int(x) for x in input().split()]
a.sort()
a.reverse()
s = 0
j = 0
for c in a:
	s += 2 ** j * c
	j += 1
print(s)


import sys
n = int(input().strip())
calories = list(map(int, input().strip().split(' ')))
calories.sort(reverse=True)
total = 0
for i in range(len(calories)):
	total += calories[i] * 2 ** i
print(total)


import sys
n = int(input().strip())
cals = list(map(int, input().strip().split(' ')))
cals.sort(reverse=True)
m = 0
for i in range(n):
	m += cals[i] * 2 ** i
print(m)


import sys
n = int(input().strip())
calories = list(map(int, input().strip().split(' ')))
calories.sort(reverse=True)
miles = 0
exp = 0
for c in calories:
	miles += c * 2 ** exp
	exp += 1
print(miles)


import sys
n = int(input().strip())
calories = list(map(int, input().strip().split(' ')))
calories = sorted(calories, reverse=True)
z = 0
for x in range(n):
	z += calories[x] * 2 ** x
print(z)


n = int(input())
a = sorted([int(i) for i in input().split()], reverse=True)
ans = 0
for i in range(len(a)):
	ans = ans + pow(2, i) * a[i]
print(ans)


import sys
n = int(input().strip())
calories = sorted(list(map(int, input().strip().split(' '))))[::-1]
j = 0
miles = 0
for i in calories:
	miles += i * 2 ** j
	j += 1
print(miles)


n = int(input().strip())
ci = list(map(int, input().strip().split()))
ci.sort(reverse=True)
miles = 0
for i in range(n):
	miles += ci[i] * pow(2, i)
print(miles)


import sys
n = int(input().strip())
calories = list(map(int, input().strip().split(' ')))
calories.sort()
calories = calories[::-1]
u = 1
res = 0
for i in range(n):
	res += calories[i] * u
	u *= 2
print(res)


import sys
n = int(input().strip())
calories = list(map(int, input().strip().split(' ')))
calories.sort(reverse=True)
(cnt, ans) = (0, 0)
for c in calories:
	ans += c * 2 ** cnt
	cnt += 1
print(ans)


n = int(input().strip())
calories = list(map(int, input().strip().split(' ')))
total = 0
for i in range(n):
	maksi = max(calories)
	total += 2 ** i * maksi
	calories.remove(maksi)
print(total)


n = int(input().strip())
C = sorted([int(x) for x in input().strip().split()], reverse=True)
miles = 0
j = 0
for c in C:
	miles += c * 2 ** j
	j += 1
print(miles)


import sys
n = int(input().strip())
calories = list(map(int, input().strip().split(' ')))
calories.sort(reverse=1)
ans = 0
for p in range(n):
	ans += pow(2, p) * calories[p]
print(ans)


import sys
n = int(input().strip())
calories = list(map(int, input().strip().split(' ')))
sorted_list = sorted(calories)[::-1]
miles = 0
for i in range(n):
	miles += sorted_list[i] * pow(2, i)
print(miles)


import sys
n = int(input().strip())
calories = list(map(int, input().strip().split(' ')))
calories = sorted(calories, reverse=True)
i = 0
m = 0
while i < n:
	m += calories[i] * 2 ** i
	i += 1
print(m)


def solution(size, arr):
	sarr = sorted(arr)
	miles = 0
	c = 0
	for i in range(len(sarr) - 1, -1, -1):
		miles += pow(2, c) * sarr[i]
		c += 1
	return miles
size = int(input())
arr = [int(t) for t in input().strip().split()]
ans = solution(size, arr)
print(str(ans))


import sys
n = int(input().strip())
calories = list(map(int, input().strip().split(' ')))
calories.sort(reverse=True)
miles = 0
for (index, calorie_amt) in enumerate(calories):
	miles += calorie_amt * 2 ** index
print(miles)


import sys
n = int(input().strip())
calories = list(map(int, input().strip().split(' ')))
ar = sorted(calories)
ar = ar[::-1]
cnt = 0
for i in range(0, n):
	cnt = cnt + 2 ** i * ar[i]
print(cnt)


n = int(input())
arr = map(int, input().split())
arr = list(arr)
arr.sort(reverse=True)
ans = 0
for i in range(n):
	ans = ans + arr[i] * 2 ** i
print(ans)


import sys
n = int(input().strip())
calories = list(map(int, input().strip().split(' ')))
steps = 0
calories.sort(reverse=True)
for i in range(n):
	steps += calories[i] * 2 ** i
print(steps)


n = int(input().strip())
cal = sorted(map(int, input().split()))
res = 0
for c in cal:
	res = res * 2 + c
print(res)


import sys
n = int(input().strip())
cal = list(map(int, input().strip().split(' ')))
cal = sorted(cal, reverse=True)
(q, l) = (0, 0)
for i in cal:
	q = q + i * 2 ** l
	l += 1
print(q)


n = int(input())
a = [int(x) for x in input().split()]
a = sorted(a)
ans = 0
for j in range(n):
	ans += 2 ** j * a[n - j - 1]
print(ans)


import sys
n = int(input().strip())
calories = list(map(int, input().strip().split(' ')))
calories.sort(reverse=True)
miles = 0
i = 0
for cal in calories:
	miles = miles + cal * 2 ** i
	i = i + 1
print(miles)


import sys
n = int(input().strip())
calories = list(map(int, input().strip().split(' ')))
calories.sort()
calories.reverse()
su = 0
for i in range(len(calories)):
	su += int(pow(2, i)) * calories[i]
print(su)


n = int(input())
c = list(map(int, input().split()))
c.sort(reverse=True)
miles = 0
for i in range(n):
	miles += c[i] * 2 ** i
print(miles)


import sys
n = int(input().strip())
calories = list(map(int, input().strip().split(' ')))
calories.sort(reverse=True)
print(sum((2 ** j * calories[j] for j in range(len(calories)))))


j = int(input())
cupcakes = [int(p) for p in input().split()]
sum = 0
for (idx, cup) in enumerate(reversed(sorted(cupcakes))):
	sum += 2 ** idx * cup
print(sum)


import sys
n = int(input().strip())
calories = list(map(int, input().strip().split(' ')))
ans = 0
calories = sorted(calories)
sz = len(calories)
for i in range(0, sz):
	ans += calories[i] * 2 ** (sz - i - 1)
print(ans)


import sys
n = int(input().strip())
calories = sorted(list(map(int, input().strip().split(' '))), reverse=True)
miles = 0
for i in range(len(calories)):
	miles += calories[i] * 2 ** i
print(miles)


import sys
n = int(input().strip())
cal = list(map(int, input().strip().split(' ')))
m = len(cal) - 1
cal.sort()
total = 0
for i in cal:
	total += i * 2 ** m
	m -= 1
print(total)


import sys
n = int(input().strip())
calories = list(map(int, input().strip().split(' ')))
calories.sort()
calories = calories[::-1]
cal = 0
for i in range(n):
	cal = cal + calories[i] * 2 ** i
print(cal)


import sys
n = int(input().strip())
calories = list(map(int, input().strip().split(' ')))
calories = sorted(calories)[::-1]
milesSum = 0
for i in range(len(calories)):
	milesSum += calories[i] * 2 ** i
print(milesSum)


import sys
n = int(input().strip())
calories = list(reversed(sorted(list(map(int, input().strip().split(' '))))))
total = 0
for (i, c) in enumerate(calories):
	total += pow(2, i) * c
print(total)


import sys
n = int(input().strip())
calories = list(map(int, input().strip().split(' ')))
c = sorted(calories, key=int, reverse=True)
sum = 0
for i in range(len(c)):
	sum += c[i] * 2 ** i
print(sum)


import sys
result = 0
n = int(input().strip())
calories = list(map(int, input().strip().split(' ')))
calories.sort()
n -= 1
for ele in calories:
	result += 2 ** n * ele
	n -= 1
print(result)


import sys
n = int(input().strip())
calories = list(map(int, input().strip().split(' ')))
calories.sort()
s = calories[::-1]
max = 0
j = 0
p = 0
for i in s:
	p = p + i * 2 ** j
	j += 1
	if p > max:
		max = p
print(max)


import sys
n = int(input().strip())
c = list(map(int, input().strip().split(' ')))
sum1 = 0
ind = 0
c = [int(i) for i in c]
c.sort(reverse=True)
for i in c:
	sum1 = sum1 + pow(2, ind) * i
	ind = ind + 1
print(sum1)


import sys
n = int(input().strip())
calories = list(map(int, input().strip().split(' ')))
calories.sort(reverse=True)
sum = 0
for i in range(len(calories)):
	sum = sum + calories[i] * 2 ** i
print(sum)


import sys
n = int(input().strip())
calories = list(map(int, input().strip().split(' ')))
walk = 0
calo = sorted(calories)
for i in range(len(calo)):
	walk += calo[len(calo) - 1 - i] * 2 ** i
print(walk)


n = int(input().strip())
cal = list(map(int, input().strip().split(' ')))
cal.sort()
cal = list(reversed(list(cal)))
d = 0
for i in range(len(cal)):
	d += cal[i] * 2 ** i
print(d)


n = int(input())
lst = sorted(list(map(int, input().split())), reverse=True)
x = 0
for i in range(n):
	x += lst[i] * 2 ** i
print(x)


import sys
n = int(input().strip())
cal = list(map(int, input().strip().split(' ')))
cal = sorted(cal, reverse=True)
ans = 0
for i in range(len(cal)):
	ans += cal[i] * 2 ** i
print(ans)


import sys
n = int(input().strip())
calories = list(map(int, input().strip().split(' ')))
calories.sort()
calories = calories[::-1]
sum = 0
for i in range(len(calories)):
	sum += calories[i] * 2 ** i
print(sum)


import sys
n = int(input().strip())
calories = list(map(int, input().strip().split(' ')))
calories.sort(reverse=True)
sum = 0
for i in range(n):
	sum += calories[i] * 2 ** i
print(sum)


import sys
n = int(input().strip())
calories = list(map(int, input().strip().split(' ')))
s_c = sorted(calories, reverse=True)
ret = 0
for (i, cal) in enumerate(s_c):
	ret += 2 ** i * cal
print(ret)


import sys
n = int(input().strip())
c = list(map(int, input().strip().split(' ')))
c.sort(reverse=True)
res = 0
for i in range(n):
	res += 2 ** i * c[i]
print(res)


import sys
n = int(input().strip())
calories = list(map(int, input().strip().split(' ')))
calories = sorted(calories, reverse=True)
x = 0
for i in range(n):
	x = x + 2 ** i * calories[i]
print(x)


import sys
n = int(input().strip())
calories = list(map(int, input().strip().split(' ')))
calories = sorted(calories)
calories.reverse()
walk = 0
for i in range(len(calories)):
	walk += 2 ** i * calories[i]
print(walk)


import sys
n = int(input().strip())
calories = list(map(int, input().strip().split(' ')))
miles = 0
cupcakes_eaten = 0
calories.sort(reverse=True)
for c in calories:
	miles = miles + c * 2 ** cupcakes_eaten
	cupcakes_eaten += 1
print(miles)


import sys
n = int(input().strip())
calories = list(map(int, input().strip().split(' ')))
calories = sorted(calories, reverse=True)
mile = 0
eaten = 0
while eaten < n:
	mile += calories[eaten] * 2 ** eaten
	eaten += 1
print(mile)


import sys
n = int(input().strip())
calories = list(map(int, input().strip().split(' ')))
calories.sort()
total = 0
for i in range(n):
	total = total + 2 ** (n - i - 1) * calories[i]
print(total)


n = int(input().strip())
assert 1 <= n <= 40
cs = [int(x) for x in input().strip().split(' ')]
cs.sort(reverse=True)
b = 1
res = 0
for i in range(n):
	res += cs[i] * b
	b <<= 1
print(res)


import sys
n = int(input().strip())
calories = list(map(int, input().strip().split(' ')))
calories = list(reversed(sorted(calories)))
x0 = 0
count = 0
for c in calories:
	x0 = x0 + c * 2 ** count
	count += 1
print(x0)


n = input()
l1 = list(map(int, input().split()))
l1.sort()
l1.reverse()
ans = 0
i = 0
for i in range(0, len(l1)):
	ans = ans + l1[i] * 2 ** i
print(ans)


import sys
n = int(input().strip())
calories = list(map(int, input().strip().split(' ')))
calories.sort(reverse=True)
result = 0
for i in range(n):
	result = result + calories[i] * 2 ** i
print(result)


import sys
n = int(input().strip())
calories = list(map(int, input().strip().split(' ')))
calories.sort(reverse=True)
eaten = 0
miles = 0
for i in range(0, n):
	miles = miles + calories[i] * pow(2, eaten)
	eaten += 1
print(miles)


import sys
n = int(input().strip())
calories = list(map(int, input().strip().split(' ')))
sorted_calories = sorted(calories, reverse=True)
miles = 0
for x in range(n):
	miles += sorted_calories[x] * 2 ** x
print(miles)


n = int(input().strip())
calories = list(map(int, input().strip().split(' ')))
calories.sort(reverse=True)
print(sum((2 ** j * c for (j, c) in enumerate(calories))))


import sys
n = int(input().strip())
c = list(map(int, input().strip().split(' ')))
sum = 0
for i in range(len(c)):
	sum = sum + int(max(c) * 2 ** i)
	c.remove(max(c))
print(sum)


import sys
n = int(input().strip())
calories = list(map(int, input().strip().split(' ')))
miles = 0
rev = sorted(calories)[::-1]
for i in range(0, len(rev)):
	miles += rev[i] * 2 ** i
print(miles)


import sys
n = int(input().strip())
calories = list(map(int, input().strip().split(' ')))
calories.sort(reverse=True)
miles = 0
for (i, c) in enumerate(calories):
	miles += 2 ** i * c
print(miles)


import sys
n = int(input().strip())
calories = list(map(int, input().strip().split(' ')))
sum = 0
calories.sort(reverse=True)
for i in range(n):
	sum += calories[i] * pow(2, i)
print(sum)


import sys
sum = 0
k = 0
n = int(input().strip())
calories = list(map(int, input().strip().split(' ')))
calories.sort(reverse=True)
for i in calories:
	sum = sum + i * 2 ** k
	k = k + 1
print(sum)


import sys
n = int(input().strip())
calories = list(map(int, input().strip().split(' ')))
calories = sorted(calories, reverse=True)
l = 0
c = 0
for i in range(n):
	l += calories[i] * 2 ** c
	c += 1
print(l)


n = int(input().strip())
c = list(map(int, input().strip().split(' ')))
a = 0
c.sort(reverse=True)
for i in range(n):
	a += c[i] * 2 ** i
print(a)


import sys
n = int(input().strip())
calories = sorted(list(map(int, input().strip().split(' '))), reverse=True)
prev = 0
result = 0
for i in range(len(calories)):
	result = result + calories[i] * 2 ** i
print(result)


import sys
n = int(input().strip())
cal = list(map(int, input().strip().split(' ')))
cal.sort()
cal.reverse()
miles = 0
for i in range(n):
	cup = cal[i] * 2 ** i
	miles += cup
print(miles)


import sys
n = int(input())
inp = input().split()
a = []
for i in inp:
	a.append(int(i))
a.sort()
s = 0
for i in range(n):
	d = a[n - i - 1] * 2 ** i
	s = s + d
print(s)


import sys
n = int(input().strip())
calories = list(map(int, input().strip().split(' ')))
calories = sorted(calories, reverse=True)
miles = 0
for cupcake in range(n):
	miles += calories[cupcake] * 2 ** cupcake
print(miles)


import sys
n = int(input().strip())
calories = list(map(int, input().strip().split(' ')))
calories.sort()
i = 0
total = 0
for c in calories:
	total += c * 2 ** (n - 1 - i)
	i += 1
print(total)


N = int(input().strip())
A = list(map(int, input().strip().split(' ')))
A.sort(reverse=True)
ans = sum([A[i] * 2 ** i for i in range(0, N)])
print(ans)


import sys
n = int(input().strip())
calories = list(map(int, input().strip().split(' ')))
result = 0
counter = 0
for i in sorted(calories, reverse=True):
	result += i * 2 ** counter
	counter += 1
print(result)


import sys
n = int(input().strip())
calories = list(map(int, input().strip().split(' ')))
calories.sort(reverse=True)
miles = 0
for i in range(n):
	miles += calories[i] * 2 ** i
print(miles)


import sys
n = int(input().strip())
calories = list(map(int, input().strip().split(' ')))
calories.sort()
calories = calories[::-1]
total = 0
for i in range(n):
	total = total + 2 ** i * calories[i]
print(total)


import sys
n = int(input().strip())
calories = list(map(int, input().strip().split(' ')))
miles = 0
count = 0
for i in range(len(calories)):
	a = max(calories)
	miles = miles + a * 2 ** count
	count = count + 1
	calories.remove(max(calories))
print(miles)


n = int(input())
a = list(map(int, input().split()))
count = 0
su = 0
for i in range(n):
	c = max(a)
	su += count + c * 2 ** i
	del a[a.index(c)]
print(su)


import sys
n = int(input().strip())
calories = list(map(int, input().strip().split(' ')))
calories.sort(reverse=True)
miles = 0
i = 0
for a in calories:
	miles += 2 ** i * a
	i += 1
print(miles)


import sys
from math import pow
n = int(input().strip())
calories = list(map(int, input().strip().split(' ')))
calories.sort(reverse=True)
miles = 0
for a0 in range(n):
	miles += calories[a0] * pow(2, a0)
print(int(miles))


import sys
n = int(input().strip())
calories = list(map(int, input().strip().split(' ')))
calories.sort()
w = 0
for i in range(len(calories)):
	w = w + 2 ** i * calories[len(calories) - 1 - i]
print(w)


import sys
n = int(input().strip())
calories = list(map(int, input().strip().split(' ')))
calories.sort()
calories.reverse()
c = 0
miles = 0
for i in calories:
	miles = miles + i * 2 ** c
	c = c + 1
print(miles)


import sys
n = int(input().strip())
calories = list(map(int, input().strip().split(' ')))
calories = sorted(calories)
calories.reverse()
total = 0
for (val, cal) in enumerate(calories):
	total += cal * 2 ** val
print(total)


import sys
n = int(input().strip())
calories = list(map(int, input().strip().split(' ')))
calories.sort(reverse=True)
(x, c) = (0, 0)
for i in calories:
	x = x + i * 2 ** c
	c += 1
print(x)


import sys
n = int(input().strip())
calories = list(map(int, input().strip().split(' ')))
calories = sorted(calories)[::-1]
total = 0
for i in range(n):
	total += calories[i] * 2 ** i
print(total)


def solve(a):
	a.sort(reverse=True)
	s = 0
	for i in range(len(a)):
		s += a[i] * 2 ** i
	return s
n = int(input())
a = list(map(int, input().split()))
print(solve(a))


n = int(input())
cup = list(map(int, input().split()))
cup.sort()
cup.reverse()
cnt = 0
for j in range(n):
	cnt = cnt + cup[j] * 2 ** j
print(cnt)


n = int(input())
l = input().split(' ')
for i in range(n):
	l[i] = int(l[i])
l.sort(reverse=True)
sum = 0
for i in range(n):
	sum = sum + l[i] * 2 ** i
print(sum)


import sys
n = int(input().strip())
calories = list(map(int, input().strip().split(' ')))
calories.sort()
calories.reverse()
miles = 0
for i in range(n):
	miles += pow(2, i) * calories[i]
print(miles)


import sys
n = int(input().strip())
calories = list(map(int, input().strip().split(' ')))
distance = 0
j = 0
calories = sorted(calories, reverse=True)
for i in range(n):
	cal = calories[i]
	distance += 2 ** j * cal
	j += 1
print(distance)


import sys
n = int(input().strip())
calories = list(map(int, input().strip().split(' ')))
max_cal = max(calories)
eaten = 0
miles = 0
while len(calories) > 0:
	miles += int(max_cal) * 2 ** eaten
	eaten += 1
	calories.remove(max_cal)
	try:
		max_cal = max(calories)
	except:
		pass
print(miles)


n = int(input())
arr = list(map(int, input().split()))
arr.sort(reverse=True)
tot = 0
for i in range(n):
	tot += 2 ** i * arr[i]
print(tot)


import sys
n = int(input().strip())
calories = sorted(list(map(int, input().strip().split(' '))), reverse=True)
miles = 0
step = 1
for i in range(n):
	miles += calories[i] * step
	step *= 2
print(miles)