Isaac has to buy a new HackerPhone for his girlfriend Amy. He is exploring the shops in the town to compare the prices whereupon he finds a shop located on the first floor of a building, that has a unique pricing policy. There are N steps leading to the shop. A numbered ball is placed on each of the steps. 

The shopkeeper gives Isaac a fair coin and asks him to toss the coin before climbing each step. If the result of the toss is a 'Heads', Isaac should pick up the ball, else leave it and proceed to the next step.

The shopkeeper then asks Isaac to find the sum of all the numbers he has picked up (let's say S). The price of the HackerPhone is then the expected value of S. Help Isaac find the price of the HackerPhone.

Input Format 

The first line of the input contains an integer N, the number of steps.
N lines follow, which are the numbers written on the ball on each step.  

Output Format 

A single line containing expected value. 

Note : Expected value must be printed as a decimal number having exactly one digit after decimal. It is guaranteed that the correct answer will have at most one digit after decimal.

Constraints 

1 <= N <= 40 

1 <= number on any ball <=10^{9}

Sample Input #00:

3
1 
1
2

Sample Output #00:

2.0

Sample Input #01:

4
1 
2
2
2

Sample Output #01:

3.5

Explanation 

In the first case there can be 8 different ways depending on the ball choice. So, we can multiply sum for each way by its probability to occur i.e. 1/8 and sum up to get the expected value as 2. 

Similarly in the second case we have 4 items , there can be 16 ways and following the expected value one gets is 3.5.

Difficulty: EASY
Tags: Probability

Starter code:

Solutions:
import sys
N = int(sys.stdin.readline())
balls = [int(sys.stdin.readline()) for _ in range(N)]
print('%.1f' % (sum(balls) / 2))


import sys

def main():
	N = sys.stdin.readline()
	K = 0
	for i in range(0, int(N)):
		K += int(sys.stdin.readline())
	print(K / 2)
main()


count = int(input())
total = 0
for i in range(count):
	total += int(input()) / 2
print(total)


import sys
from collections import deque
import heapq
from math import *
from itertools import *
PI = pi
INF = 1000000000

def gl():
	return input()

def gs():
	return (x for x in input().split())

def gi():
	return int(input())

def gis():
	return (int(x) for x in input().split())

def gf():
	return float(input())

def gfs():
	return (float(x) for x in input().split())

def even(x):
	return x % 2 == 0

def odd(x):
	return x % 2 == 1

def dbg(s):
	print(s, file=sys.stderr)
N = gi()
list_ = []
for i in range(N):
	list_.append(int(gi()))
print('%.1f' % (sum(list_) / 2))


n = int(input())
sum = 0
for i in range(n):
	a = int(input())
	sum += 2 ** (n - 1) * a
print('{0:.1f}'.format(sum / 2 ** n))


def main():
	n = int(input())
	arrData = []
	p = 2 ** n
	tempResult = 0
	for i in range(0, n):
		num = int(input())
		tempResult += num * (p / 2)
	result = 1 / p * tempResult
	print(result)
main()


from decimal import *
getcontext().prec = 1
num_steps = int(input())
ans = 0
for i in range(num_steps):
	num = int(input())
	ans = ans + num
ans = ans / 2
print('{}'.format(ans))


import sys
N = int(sys.stdin.readline())
xs = [int(n) for n in sys.stdin.read().split()]
print('{0:.1f}'.format(sum(xs) / 2.0))


n = int(input())
sum = 0
for i in range(0, n):
	x = int(input())
	sum += x
sum /= 2
print('%.1f' % sum)


numBalls = int(input())
expectedValue = 0
for case in range(0, numBalls):
	ballValue = int(input())
	expectedValue += ballValue * 0.5
print('%.1f' % expectedValue)


N = int(input())
balls = map(int, [input() for x in range(N)])
print(sum(balls) / 2)


import sys
T = int(input())
a = 0
while T > 0:
	a += int(input())
	T -= 1
k = str(a / 2)
print(k[:k.index('.') + 2])


n = int(input())
a = []
for i in range(n):
	t = int(input())
	a.append(t)
dp = [0 for i in range(n)]
for i in range(n):
	if i > 0:
		dp[i] = dp[i - 1] * 2
	dp[i] += 2 ** i * a[i]
print(dp[n - 1] / 2 ** n)


N = int(input())
count = 0
for i in range(N):
	count += int(input()) / 2
print(count)


steps = int(input())
result = 0
for i in range(0, steps):
	result += int(input())
result = result / 2
result = round(result, 1)
print(result)


s = 0
n = int(input())
for i in range(0, n):
	val = int(input())
	s = s + val
print(s / 2)


lstPrices = []
for case in range(int(input())):
	lstPrices.append(int(input()))
print('%.1f' % (sum(lstPrices) / 2))


N = int(input())
val = 0
for i in range(N):
	n = int(input())
	val += n / 2
print(val)


N = int(input())
val = 0.0
for _ in range(N):
	val += 1 / 2 * int(input())
print(val)


n = int(input())
s = 0
for _ in range(n):
	s += int(input())
print('%.1f' % (s / 2))


n = int(input())
z = []
for i in range(0, n):
	x = int(input())
	z.append(x)
print(sum(z) / 2)


N = int(input())
count = 0
for i in range(0, N):
	count += int(input())
print('{:.1f}'.format(count / 2))


import math

def Solve(List):
	Total = 0
	for Value in List:
		Total += Value
	print(Total / 2)
NumberOfSteps = int(input())
StepValue = []
for Value in range(NumberOfSteps):
	StepValue.append(int(input()))
Solve(StepValue)


N = int(input())
steps = []
for i in range(N):
	steps.append(int(input()))
price = 0
for i in steps:
	price += i
print(price / 2)


n = int(input())
sum = 0
for i in range(n):
	sum += int(input())
print(sum / 2)


def main():
	N = int(input())
	sum = 0
	for i in range(N):
		sum += int(input())
	print(sum / 2)
main()


n = int(input())
total = 0
for i in range(n):
	total += int(input())
print(total / 2)


n = int(input())
x = 0
for i in range(n):
	m = int(input())
	x = m + x
x = x / 2
print(x)


times = int(input())
sol = 0
for i in range(0, times):
	sol += int(input())
print(sol / 2)


n = int(input())
ret = 0.0
for i in range(n):
	ret += int(input()) / 2
print(ret)


n = int(input())
i = 0
ball = list()
temp = 0
sum = 0
while i < n:
	temp = int(input())
	ball.append(temp)
	sum = sum + temp
	i = i + 1
sum = round(sum / 2, 1)
print(sum)


N = int(input())
s = 0
for i in range(N):
	s += 0.5 * int(input())
print(str(s))


N = int(input())
e = 0
while N > 0:
	e += int(input())
	N -= 1
print('{:.1f}'.format(e * 0.5))


n = int(input())
balls = []
for i in range(0, n):
	balls.append(int(input()))
print(sum(balls) / 2)


T = int(input())
count = 0
for i in range(T):
	count += int(input()) / 2
print(count)


s = 0.0
for i in range(int(input())):
	s += 0.5 * int(input())
print(s)


numtests = int(input())
tests = []
for i in range(numtests):
	tests.append(int(input()))
E = 0
for i in range(numtests):
	E = E + 1 / 2 * int(tests[i])
print(E)


a = int(input())
c = 0
for x in range(0, a):
	b = int(input())
	c = c + b / 2
print(c)


n = int(input())
s = 0
for i in range(n):
	s += int(input())
print('%.1f' % (0.5 * s))


N = int(input())
s = 0
for n in range(0, N):
	s += int(input())
print(s / 2)


t = int(input())
c = 0
sum = 0
while t > c:
	q = int(input())
	sum += q
	c += 1
print(0.5 * sum)


import sys

def main():
	n = int(sys.stdin.readline())
	tot = 0
	for _ in range(n):
		p = int(sys.stdin.readline())
		tot += p
	print(tot / 2)
main()


T = int(input())
s = 0
for i in range(T):
	s += int(input())
print(s / 2)


s = 0
for line in range(int(input())):
	s += int(input())
print('{:.1f}'.format(s / 2))


import sys
N = int(sys.stdin.readline())
balls = [int(sys.stdin.readline()) for _ in range(N)]
print('%.1f' % (sum(balls) / 2))


n = int(input())
numbers = []
i = 0
while i < n:
	numbers.insert(i, int(input()))
	i = i + 1
probability = 2 ** n
total_sum = sum(numbers)
sum_of_subsets = probability / 2 * total_sum
s = sum_of_subsets / probability
print(s)


import sys
n = int(sys.stdin.readline())
S = 0
for i in range(n):
	S += int(sys.stdin.readline())
print(S / 2.0)


N = int(input())
count = 0.0
for i in range(0, N):
	x = int(input())
	count += x
print(count / 2)


N = int(input())
B = []
for n in range(N):
	B.append(int(input()))
print(sum(B) / 2)


import sys
N = int(sys.stdin.readline())
the_sum = 0
for ball in range(N):
	the_sum += int(sys.stdin.readline())
print(the_sum / 2)


balls = []
N = int(input())
for n in range(N):
	balls.append(int(input()))
print(sum(balls) / 2)


N = int(input())
s = sum((int(input()) for i in range(N))) / 2.0
print(s)


N = int(input())
expectedValue = 0.0
for n in range(N):
	expectedValue += float(input()) * 0.5
print(expectedValue)


N = int(input())
balls = [int(input()) for i in range(N)]
print('{:.1f}'.format(sum(balls) / 2))


def f(l):
	if len(l) == 1:
		return l[0]
	else:
		x = 2 * f(l[1:])
		x += 2 ** (len(l) - 1) * l[0]
		return x
t = int(input())
l = []
for i in range(t):
	l.append(int(input()))
print(f(l) / 2 ** len(l))


sum = 0
for i in range(int(input())):
	sum += int(input())
print(round(sum * 0.5, 1))


tc = int(input())
summ = 0
for i in range(tc):
	summ += int(input())
print('%.1f' % (summ / 2))


N = int(input())
total = 0
for _ in range(N):
	total += int(input()) / 2
print(round(total, 1))


total = 0
for N in range(int(input())):
	total = total + int(input())
print('%.1f' % (total / 2))


lines = int(input())
res = 0
for i in range(lines):
	res += int(input())
print('%.1f' % (0.5 * res))


print(sum((int(input()) / 2 for case in range(int(input())))))


numSteps = int(input())
print('%0.1f' % (sum([int(input()) for i in range(0, numSteps)]) / 2))


n = int(input())
sum = 0
for i in range(n):
	x = int(input())
	sum += 0.5 * x
print(sum)


n = int(input())
print(sum((int(input()) for _ in range(n))) / 2)


x = int(input())
counter = 0.0
for y in range(0, x):
	k = int(input())
	counter += k
m = float(counter / 2)
print(m)


t = int(input())
assert 1 <= t <= 40
total = 0
for i in range(t):
	n = int(input())
	assert 1 <= n <= 10 ** 9
	total += n * 0.5
print(total)


z = [int(input()) for i in range(int(input()))]
print(sum(z) / 2)


n = int(input())
price = 0.0
for _ in range(n):
	pi = float(input())
	price += pi / 2
print(price)


n = int(input())
args = [int(input()) for i in range(n)]
print(sum(args) / 2)


steps = int(input())
ans = 0
for i in range(steps):
	ans += int(input())
print(ans / 2)


steps = int(input())
if 1 <= steps <= 40:
	sumNum = 0
	for s in range(0, steps):
		number = int(input())
		if 1 <= number <= 10 ** 9:
			sumNum = sumNum + number / 2
	print(sumNum)


n = int(input())
result = 0
for i in range(n):
	result = result + int(input()) / 2
print(result)


N = input()
N = int(N)
a = 0
for blah in range(N):
	a += float(input()) / 2.0
a = round(a, 1)
print(a)


N = int(input())
prob = 0
for i in range(N):
	prob += int(input())
print(prob / 2)


N = int(input())
balls = [int(input()) for i in range(N)]
total = 0.0
for (i, ball) in enumerate(balls):
	total += ball
print(total / 2.0)


n = int(input())
s = 0
for i in range(n):
	inp = int(input())
	s += inp
print(s / 2)


import sys
N = int(sys.stdin.readline())
balls = [int(sys.stdin.readline()) for _ in range(N)]
print('%.1f' % (sum(balls) / 2))


N = int(input())
balls = []
for i in range(N):
	balls.append(int(input()))
S = 0
for ball in balls:
	S += 0.5 * ball
print(S)


N = int(input())
total = 0
for _ in range(N):
	total += int(input())
print(format(total / 2, '2.1f'))


no_test = int(input())
n = 0
for i in range(no_test):
	n = n + int(input())
print(n / 2)


c = input()
z = 0
for i in range(int(c)):
	b = input()
	t = int(b) / 2
	z = z + t
print(z)


steps = int(input())
ev = 0
for step in range(steps):
	ev += int(input()) / 2
print(ev)


n = int(input())
sum = 0
for x in range(n):
	sum += int(input())
print(sum / 2)


t = int(input())
count = 0
while t > 0:
	n = int(input())
	count += n / 2
	t = t - 1
print(count)


def GetPrice(Balls):
	B = Balls[::-1]
	n = len(B)
	tot = 0
	for i in range(0, n):
		tot = tot + B[i] / 2
	tot = 100 * tot // 10
	return tot / 10
N = int(input())
Balls = []
while N:
	N = N - 1
	Balls.append(int(input()))
print(GetPrice(Balls))


print(sum((int(input()) for _ in range(int(input())))) / 2)


sum = 0
for _ in range(int(input())):
	sum += int(input()) / 2
print(sum)


import sys
import re
data = sys.stdin.readlines()
balls = re.findall('\\d+', ' '.join(data[1:]))
print(sum(map(int, balls)) / 2)


cases = int(input())
ex_v = 0
for i in range(cases):
	ex_v += int(input())
print(ex_v / 2)


N = int(input())
sum = 0
for i in range(N):
	sum = sum + int(input())
print(sum / 2)


cases = int(input())
ar_in = []
for i in range(cases):
	ar_in.append(int(input()))
pos = 2 ** cases
erg = 0
product = 2 ** (cases - 1)
for j in ar_in:
	erg += product * j
erg2 = float(erg * (1 / pos))
out1 = '{0:0.1f}'.format(erg2)
print(out1)


def solution():
	n = int(input())
	balls = [input() for _ in range(n)]
	return sum(map(lambda b: float(b) / 2.0, balls))
print(solution())


nbTestCase = int(input())
i = 0
probability = 1 / 2
num = 0
res = 0
while i < nbTestCase:
	numOnBall = int(input())
	res += probability * numOnBall
	i += 1
print(res)


import math
N = int(input())
expected_value = 0
for i in range(0, N):
	expected_value = expected_value + math.pow(2, N - 1) * int(input())
print(0.5 * (expected_value / math.pow(2, N - 1)))


t = int(input())
print('%.1lf' % (float(sum([int(input()) for i in range(t)])) / 2))


n = int(input())
s = sum([int(input()) for i in range(n)]) / 2
print('%.1f' % s)


import itertools

def main():
	numbers = [int(input()) for x in range(int(input()))]
	expected_value = 0
	for n in numbers:
		expected_value += n * 2 ** (len(numbers) - 1)
	print(1 / 2 ** len(numbers) * expected_value)

def combinations(n):
	for i in range(2 ** n):
		t1 = '{0:b}'.format(i)
		t = '0' * (n - len(t1)) + t1
		yield [int(x) for x in list(t)]
main()


s = 0
for i in range(int(input())):
	s += int(input())
print(s / 2)