Wet Shark once had 2 sequences: 
{a_n}= {a_1, a_2, a_3, ... , a_(109)}  
{b_n} = {b_1, b_2, b_3, ... , b_(109)}  
However, he only kept one element from each sequence. Luckily, both the elements that Wet Shark kept have the same index in Wet Shark's sequences: that is, he took a_i and b_i for some 1 ≤ i ≤ 109. 
Right after Wet Shark loses his sequences, he finds that he actually needs them to break the code of Cthulhu to escape a labyrinth. Cthulhu's code is a single floating point number Q. However, the code verifier is faulty. If Wet Shark enters any code c such that |c - Q| ≤ 0.01 , Cthulhu's code checker will allow him to escape.
Wet Shark now starts to panic, and consults Dry Dolphin for help via ultrasonic waves. After the Dry Dolphin Sequence Processing Factory processes data of Wet Shark's sequences, the machines give Wet Shark the following 2 relations his sequences follow for all 1 ≤ n < 109, where x = sqrt(2) and y = sqrt(3).

Wet Shark is now clueless on how to compute anything, and asks you for help.
Wet Shark has discovered that Cthulhu's code is actually defined as Q = (a_k + b_k) / (2^s), where s is a predetermined number, k is the index of another element in Wet Shark's sequence, and a_k, b_k are precisely the kth elements of Wet Shark's sequences {a_n} and {b_n}, respectively.
Given k, i, and the 2 elements of the arrays Wet Shark has lost, find any value of the code c that will allow Wet Shark to exit Cthulhu's labyrinth.

-----Input-----
The first line of input contains 3 space separated integers i, k, s — the common index of the two elements Wet Shark kept, the index of Wet Shark's array needed to break Cthulhu's code, and the number s described in the problem statement, respectively. It is guaranteed that Cthulhu's code, Q, is between -109 and 109 (both inclusive).
The second line of the input contains 2 space separated integers a_i and b_i, representing the ith element of sequence {a_n} and the ith element of sequence {b_n}, respectively.

-----Output-----
Output any number c that will crack Cthulhu's code. Recall that if Wet Shark enters any code c such that |c - Q| ≤ 0.01 , Cthulhu's code checker will allow him to exit the labyrinth.

----- Constraints -----
-   SUBTASK 1: 20 POINTS  
-  1 ≤ i ≤ 103 
-  1 ≤ k ≤ 103 
-  -103 ≤ s ≤ 103 
-  1 ≤ a_i, b_i ≤ 103 

-   SUBTASK 2: 80 POINTS  
-  1 ≤ i ≤ 1010 
-  1 ≤ k ≤ 1010 
-  -1010 ≤ s ≤ 1010 
-  1 ≤ a_i, b_i ≤ 1010 
It is guaranteed that -1010 ≤ Q ≤  1010.

-----Example-----
Input:
1 1 5
4 5

Output:
0.28125

-----Explanation-----
Example case 1. In this case, a_1 = 4, b_1 = 5, and s = 5. Cthulhu's code in this case is (a_1 + b_1) / (2s) = 9/32 = 0.28125.

Source: codechef | Difficulty: HARD
Tags: Matrices

Data structures

Complete search


Solutions:
from math import *

def main():
	inp = list(map(int, input().split()))
	i = inp[0]
	k = inp[1]
	s = inp[2]
	inp = list(map(int, input().split()))
	ai = inp[0]
	bi = inp[1]
	x = 2.0 ** 0.5
	y = 3.0 ** 0.5
	h = k - i
	ak = 0
	bk = 0
	if abs(h) % 2 == 1:
		ak = float(2 ** (floor(h / 2) + float(h) / 2.0 + 2 * floor(h / 2) - s) * (float(ai + bi) - y * float(ai - bi)))
		bk = float(2 ** (floor(h / 2) + float(h) / 2.0 + 2 * floor(h / 2) - s) * (float(ai - bi) + y * float(ai + bi)))
	else:
		ak = float(2 ** (floor(h / 2) + float(h) / 2.0 + 2 * floor(h / 2) - s) * float(ai))
		bk = float(2 ** (floor(h / 2) + float(h) / 2.0 + 2 * floor(h / 2) - s) * float(bi))
	Q = ak + bk
	print(Q)
main()


X = pow(2, 0.5)
Y = pow(3, 0.5)

def calculateCode(i, ai, bi, k, s):
	if (k - i) % 2 != 0:
		(ai, bi) = (X * (ai + bi) - X * Y * (ai - bi), X * (ai - bi) + X * Y * (ai + bi))
		i += 1
	return (ai + bi) * pow(2, 2 * (k - i) - s)
(i, k, s) = [int(x) for x in input().split()]
(ai, bi) = [int(x) for x in input().split()]
print(calculateCode(i, ai, bi, k, s))


import math
x = math.sqrt(2)
y = math.sqrt(3)
inp = input().strip()
inl = inp.split(' ')
i = int(inl[0])
k = int(inl[1])
s = int(inl[2])
inp = input().strip()
inl = inp.split(' ')
ai = int(inl[0])
bi = int(inl[1])
ak = 0
bk = 0
if (i - k) % 2 == 1:
	ai2 = x * (ai + bi) - x * y * (ai - bi)
	bi2 = x * (ai - bi) + x * y * (ai + bi)
	ai = ai2
	bi = bi2
	i = i + 1
ep = 4
ans = ai + bi
ep = ep * int((k - i) / 2)
pw = ep - s
ans = ans * 2 ** pw
print(ans)


zz = input()
(i, k, s) = [int(x) for x in zz.split()]
zz = input()
(ai, bi) = [int(x) for x in zz.split()]
import math
x = math.sqrt(2)
y = math.sqrt(3)
if i > k:
	if (i - k) % 2 == 0:
		s = s + 2 * (i - k)
		q = (ai + bi) / 2 ** s
	else:
		k_new = k - 1
		a = x * (ai + bi) - x * y * (ai - bi)
		b = x * (ai - bi) + x * y * (ai + bi)
		s = s + 2 * (i - k_new)
		q = (a + b) / 2 ** s
elif i == k:
	q = (ai + bi) / 2 ** s
elif (k - i) % 2 == 0:
	s = s - 2 * (k - i)
	q = (ai + bi) / 2 ** s
else:
	k_new = k - 1
	a = x * (ai + bi) - x * y * (ai - bi)
	b = x * (ai - bi) + x * y * (ai + bi)
	s = s - 2 * (k_new - i)
	q = (a + b) / 2 ** s
print(q)


X = pow(2, 0.5)
Y = pow(3, 0.5)
maxI = pow(10, 10)
maxK = pow(10, 10)
maxS = pow(10, 10)

def calculateCode(i, ai, bi, k, s):
	c = 0
	(aii, bii) = (ai, bi)
	if (k - i) % 2 != 0:
		(aii, bii) = (X * (ai + bi) - X * Y * (ai - bi), X * (ai - bi) + X * Y * (ai + bi))
		i += 1
	exp = 2 * (k - i) - s
	return (aii + bii) * pow(2, exp)
(i, k, s) = [int(x) for x in input().split()]
(ai, bi) = [int(x) for x in input().split()]
result = calculateCode(i, ai, bi, k, s)
print(result)


from math import *
(i, k, s) = (float(x) for x in input().split(' '))
(ai, bi) = (float(x) for x in input().split(' '))
x = sqrt(2)
y = sqrt(3)
if i == k:
	print((ai + bi) / pow(2, s))
elif k > i:
	if (k - i) % 2 == 0:
		print((ai + bi) * pow(2, (k - i) * 2 - s))
	else:
		print(pow(2, 2 * k - 1 - 2 * i - s) * (ai + bi * y) * x)
elif (i - k) % 2 == 0:
	print((ai + bi) * pow(2, 2 * (k - i) - s))
else:
	print(pow(2, 2 * k - 1 - 2 * i - s) * (ai + bi * y) * x)


import math

def main():
	IN = '11 6 5'
	z = IN.split()
	z = input().split()
	i = int(z[0])
	k = int(z[1])
	s = int(z[2])
	IN = '4 5'
	z = IN.split()
	z = input().split()
	a_i = int(z[0])
	b_i = int(z[1])
	x = math.sqrt(2)
	y = math.sqrt(3)
	if i <= k:
		diff = k - i
		if (k - i) % 2 == 0:
			ans = (a_i + b_i) * math.pow(2, 2 * (k - i) - s)
		else:
			ans = (2 * x * a_i + 2 * x * y * b_i) * math.pow(2, 2 * (k - (i + 1)) - s)
			diff = int(diff / 2)
			ans = (2 * x * a_i + 2 * x * y * b_i) * math.pow(2, 4 * diff - s)
	else:
		diff = i - k
		if (i - k) % 2 == 0:
			ans = (a_i + b_i) / math.pow(2, 2 * (i - k) + s)
		else:
			ans = (2 * x * a_i + 2 * x * y * b_i) / math.pow(2, 2 * (i + 1 - k) + s)
			diff = int(diff / 2)
			ans = (2 * x * a_i + 2 * x * y * b_i) / math.pow(2, 4 * diff + 4 + s)
	print(ans)
main()


from math import *
a = list(map(int, input().split()))
b = list(map(int, input().split()))
p = (a[1] - a[0]) % 2
q = a[1] - a[0] >> 1
q = p + (q << 2) - a[2]
ans = pow(2, q) * pow(sqrt(2), p) * (b[0] + b[1] * pow(sqrt(3), p))
print('%.10f' % ans)


def recrel(k, i, ai, bi, s):
	n = k - i
	if n == 0:
		return (ai + bi) / 2 ** s
	elif n % 2 == 0:
		return 2 ** (2 * n - s) * (ai + bi)
	else:
		return 2 ** (2 * n - (1 + s)) * (2 ** 0.5 * ai + 6 ** 0.5 * bi)

def recrel1(k, i, ai, bi, s):
	n = i - k
	if n == 0:
		return ai + bi
	elif n % 2 == 0:
		return (ai + bi) / 2 ** (2 * n + s)
	else:
		return (2 ** 0.5 * ai + 6 ** 0.5 * bi) / 2 ** (2 * n + 1 + s)
(i, k, s) = input().split(' ')
i = int(i)
k = int(k)
s = float(s)
(ai, bi) = input().split(' ')
ai = int(ai)
bi = int(bi)
if k >= i:
	q = recrel(k, i, ai, bi, s)
	print(round(q, 5))
elif k < i:
	q = recrel1(k, i, ai, bi, s)
	print(round(q, 5))


x = 2 ** 0.5
y = 3 ** 0.5

def crack(i, k, s, a_i, b_i):
	p = x * (1 - y)
	q = x * (1 + y)
	sq = p * p + q * q
	d = k - i
	if d % 2 != 0:
		i = i + 1
		a_i_1 = a_i
		b_i_1 = b_i
		a_i = p * a_i_1 + q * b_i_1
		b_i = q * a_i_1 - p * b_i_1
		d = k - i
	multiplier = 2 ** (d / 2 * 4 - s)
	a_k = a_i * multiplier
	b_k = b_i * multiplier
	return (a_k, b_k)
[i, k, s] = map(int, input().split())
[a_i, b_i] = map(int, input().split())
(a_k, b_k) = crack(i, k, s, a_i, b_i)
Q = a_k + b_k
print('%f' % Q)


from math import atan
from math import pi
from math import cos
from math import sin

def findAngle(x, y):
	if x > 0 and y == 0:
		return 0
	if x < 0 and y == 0:
		return pi
	if x == 0 and y > 0:
		return pi / 2
	if x == 0 and y < 0:
		return 3 * pi / 2
	if x > 0 and y > 0:
		return atan(y / (x + 0.0))
	if x < 0 and y > 0:
		return pi + atan(y / (x + 0.0))
	if x < 0 and y < 0:
		return pi + atan(y / (x + 0.0))
	if x > 0 and y < 0:
		return 2 * pi + atan(y / (x + 0.0))

def findArg(x, y, m, n):
	angle = findAngle(x, y)
	if m % 2 == n % 2:
		return angle
	else:
		return (7 / 12.0 * pi - angle) % (2 * pi)
(i, k, q) = map(int, input().split(' '))
(a_i, b_i) = map(float, input().split(' '))
length = (a_i ** 2 + b_i ** 2) ** 0.5
angle = findArg(a_i, b_i, i, k)
ak = cos(angle) * length
bk = sin(angle) * length
print(2 ** (2 * (k - i) - q) * (ak + bk))


def main():
	line = list(map(int, input().split()))
	i = line[0]
	k = line[1]
	s = line[2]
	line = list(map(int, input().split()))
	aI = line[0]
	bI = line[1]
	root2 = 2 ** 0.5
	root3 = 3 ** 0.5
	root6 = float(root2) * float(root3)
	if i % 2 == 0:
		powerOf2 = 2 * i
		if k % 2 == 0:
			powerOf2InQ = s - 2 * k + powerOf2
			print('%.4f' % (float(aI + bI) / float(2 ** powerOf2InQ)))
		else:
			powerOf2InQ = s - 2 * (k - 1) + powerOf2
			aPlusB = aI + bI
			aMinusB = aI - bI
			a1 = root2 * aPlusB - root6 * aMinusB
			b1 = root2 * aMinusB + root6 * aPlusB
			print('%.4f' % (float(a1 + b1) / float(2 ** powerOf2InQ)))
	else:
		powerOf2 = 2 * (i - 1)
		if k % 2 == 1:
			powerOf2InQ = s - 2 * (k - 1) + powerOf2
			print('%.4f' % (float(aI + bI) / float(2 ** powerOf2InQ)))
		else:
			powerOf2InQ = s - 2 * k + powerOf2
			a0 = ((2 + root3) * bI - aI) / (4 * root2 * (1 + root3))
			b0 = (aI * (1 + root3) - bI * (1 - root3)) / (8 * root2)
			print('%.4f' % (float(a0 + b0) / float(2 ** powerOf2InQ)))
	return 0
main()


i_k_s = input().split()
i = int(i_k_s[0])
k = int(i_k_s[1])
s = int(i_k_s[2])
a_b = input().split()
a = int(a_b[0])
b = int(a_b[1])
if (k - i) % 2 == 0:
	x = 2 ** (2 * (k - i) - s) * (a + b)
else:
	a1 = 2 ** (1 / 2.0) * (a + b) - 6 ** (1 / 2.0) * (a - b)
	b1 = 2 ** (1 / 2.0) * (a - b) + 6 ** (1 / 2.0) * (a + b)
	x = 2 ** (2 * (k - i - 1) - s) * (a1 + b1)
print(x)


(k, i, s) = map(int, input().split())
(ai, bi) = map(int, input().split())
if i == k:
	print((ai + bi) / pow(2, s))
else:
	if (i - k) % 2 == 1:
		si = (ai + 1.7320508075688772 * bi) / (4 * 1.4142135623730951)
		i = int((i - k + 1) / 2)
	else:
		si = ai + bi
		i = int((i - k) / 2)
	print(si * pow(2, 4 * i - s))


from math import *
(i, k, s) = list(map(int, input().split(' ')))
(a, b) = list(map(float, input().split(' ')))
Si = a + b
if i % 2 != k % 2:
	Si = 2 * sqrt(2) * a + 2 * sqrt(6) * b
	i += 1
print(pow(2, 2 * (k - i) - s) * Si)


import math
(i, k, s) = map(int, input().split())
(a, b) = map(int, input().split())
next1 = (math.sqrt(2) + math.sqrt(6)) * (a + b) + (math.sqrt(2) - math.sqrt(6)) * (a - b)
if k == i:
	print((a + b) * pow(0.5, s))
elif k > i:
	temp = k - i
	if temp % 2 == 0:
		power = temp / 2
		print(pow(2, power * 4 - s) * (b + a))
	elif temp % 2 != 0:
		power = (temp - 1) / 2
		print(pow(2, power * 4 - s) * next1)
elif k < i:
	temp = i + 1 - k
	if temp % 2 == 0:
		power = temp / 2
		print(pow(1 / 2, power * 4 + s) * next1)
	elif temp % 2 != 0:
		power = (temp - 1) / 2
		print(pow(1 / 2, power * 4 + s) * (a + b))


import math
a = [int(x) for x in input().split()]
i = a[0]
k = a[1]
s = a[2]
b = [float(x) for x in input().split()]
x = math.sqrt(2)
y = math.sqrt(3)
sum = 0
diff = 0
if k >= i:
	p16 = int((k - i) / 2)
	if s >= 0:
		ps = int(s / 4)
		s %= 4
		p = p16 - ps
		if p >= 0:
			b[0] *= math.pow(16, p)
			b[1] *= math.pow(16, p)
			if (k - i) % 2 != 0:
				sum = b[0] + b[1]
				diff = b[1] - b[0]
				b[0] = x * sum + x * y * diff
				b[1] = x * y * sum - x * diff
			sum = b[0] + b[1]
			for j in range(s):
				sum /= 2
		else:
			p = -p
			b[0] /= math.pow(16, p)
			b[1] /= math.pow(16, p)
			if (k - i) % 2 != 0:
				sum = b[0] + b[1]
				diff = b[1] - b[0]
				b[0] = x * sum + x * y * diff
				b[1] = x * y * sum - x * diff
			sum = b[0] + b[1]
			for j in range(s):
				sum /= 2
	else:
		ps = int(s / 4)
		s %= 4
		s = (4 - s) % 4
		p = p16 + ps
		if p >= 0:
			b[0] *= math.pow(16, p)
			b[1] *= math.pow(16, p)
			if (k - i) % 2 != 0:
				sum = b[0] + b[1]
				diff = b[1] - b[0]
				b[0] = x * sum + x * y * diff
				b[1] = x * y * sum - x * diff
			sum = b[0] + b[1]
			for j in range(s):
				sum *= 2
		else:
			p = -p
			b[0] /= math.pow(16, p)
			b[1] /= math.pow(16, p)
			if (k - i) % 2 != 0:
				sum = b[0] + b[1]
				diff = b[1] - b[0]
				b[0] = x * sum + x * y * diff
				b[1] = x * y * sum - x * diff
			sum = b[0] + b[1]
			for j in range(s):
				sum *= 2
else:
	den = 8 * x
	p16 = int((i - k) / 2)
	if s >= 0:
		ps = int(s / 4)
		s %= 4
		p = p16 - ps
		if p >= 0:
			b[0] /= math.pow(16, p)
			b[1] /= math.pow(16, p)
			if (i - k) % 2 != 0:
				sum = b[0] + b[1]
				diff = b[1] - b[0]
				b[1] = (y * sum - diff) / den
				b[0] = (sum + y * diff) / den
			sum = b[0] + b[1]
			for j in range(s):
				sum /= 2
		else:
			p = -p
			b[0] *= math.pow(16, p)
			b[1] *= math.pow(16, p)
			if (i - k) % 2 != 0:
				sum = b[0] + b[1]
				diff = b[1] - b[0]
				b[1] = (y * sum - diff) / den
				b[0] = (sum + y * diff) / den
			sum = b[0] + b[1]
			for j in range(s):
				sum /= 2
	else:
		ps = int(s / 4)
		s %= 4
		s = (4 - s) % 4
		p = p16 + ps
		if p >= 0:
			b[0] /= math.pow(16, p)
			b[1] /= math.pow(16, p)
			if (i - k) % 2 != 0:
				sum = b[0] + b[1]
				diff = b[1] - b[0]
				b[1] = (y * sum - diff) / den
				b[0] = (sum + y * diff) / den
			sum = b[0] + b[1]
			for j in range(s):
				sum *= 2
		else:
			p = -p
			b[0] *= math.pow(16, p)
			b[1] *= math.pow(16, p)
			if (i - k) % 2 != 0:
				sum = b[0] + b[1]
				diff = b[1] - b[0]
				b[1] = (y * sum - diff) / den
				b[0] = (sum + y * diff) / den
			sum = b[0] + b[1]
			for j in range(s):
				sum *= 2
print(sum)


import math
(i, k, s) = input().split()
i = int(i)
k = int(k)
s = int(s)
(a_i, b_i) = input().split()
a_i = float(a_i)
b_i = float(b_i)
plus = math.sqrt(2) + math.sqrt(6)
minus = math.sqrt(6) - math.sqrt(2)
if i % 2 == 0:
	s1 = 2 * (i - 2)
	b1 = (plus * a_i + minus * b_i) / 16
	a1 = (plus * b1 - a_i) / minus
else:
	s1 = 2 * (i - 1)
	b1 = b_i
	a1 = a_i
if k % 2 == 0:
	s2 = 2 * (k - 2)
	ak = plus * b1 - minus * a1
	bk = plus * a1 + minus * b1
else:
	s2 = 2 * (k - 1)
	ak = a1
	bk = b1
Q = pow(2, s2 - s1 - s) * (ak + bk)
print(Q)


import math
(i, k, s) = map(int, input().split())
(ai, bi) = map(float, input().split())
ans = 1.0
if k >= i:
	if (k - i) % 2 == 0:
		power = 2 * (k - i) - s
		if power >= 0:
			ans = ai + bi
			ans *= pow(2, power)
		else:
			power = abs(power)
			ans = ai + bi
			while power > 0:
				ans /= 2
				power -= 1
	else:
		power = (k - i) // 2
		power = 4 * power - s
		if power >= 0:
			while power > 0:
				ai *= 2
				bi *= 2
				power -= 1
		else:
			power = abs(power)
			while power > 0:
				ai /= 2
				bi /= 2
				power -= 1
		ai *= 2 * math.sqrt(2)
		bi *= 2 * math.sqrt(6)
		ans = ai + bi
elif (i - k) % 2 == 0:
	power = 2 * (i - k) + s
	ans = ai + bi
	if power < 0:
		power = abs(power)
		ans *= pow(2, power)
	else:
		while power > 0:
			ans /= 2
			power -= 1
else:
	power = (i - k) // 2
	power = 4 * power + s
	if power < 0:
		power = abs(power)
		while power > 0:
			ai *= 2
			bi *= 2
			power -= 1
	else:
		while power > 0:
			ai /= 2
			bi /= 2
			power -= 1
	ai *= math.sqrt(2) / 8.0
	bi *= math.sqrt(6) / 8.0
	ans = ai + bi
print('{:.8f}'.format(ans))


from math import *
from decimal import *
getcontext().prec = 200
args1 = input().split(' ')
args2 = input().split(' ')
I = int(args1[0])
K = int(args1[1])
S = Decimal(args1[2])
A = Decimal(args2[0])
B = Decimal(args2[1])
s2 = Decimal(2.0) ** Decimal(0.5)
s6 = Decimal(6.0) ** Decimal(0.5)
a1 = s2 * (A + B) - s6 * (A - B)
af1 = a1 / A
b1 = s2 * (A - B) + s6 * (A + B)
bf1 = b1 / B
a2 = s2 * (a1 + b1) - s6 * (a1 - b1)
af2 = a2 / a1
b2 = s2 * (a1 - b1) + s6 * (a1 + b1)
bf2 = b2 / b1
d2 = Decimal(2.0)
ak = A
bk = B
if K >= I:
	p = Decimal((K - I) // 2)
	s = S
	c = 0
	while fabs(p) > 1.0 or fabs(s) > 1.0:
		p /= d2
		s /= d2
		c += 1
	c2 = Decimal(2 ** c)
	ak *= ((af1 * af2) ** p / d2 ** s) ** c2
	bk *= ((bf1 * bf2) ** p / d2 ** s) ** c2
	if (K - I) % 2 == 1:
		ak *= af1
		bk *= bf1
else:
	p = Decimal((I - K) // 2)
	s = S
	c = 0
	while fabs(p) > 1.0 or fabs(s) > 1.0:
		p /= d2
		s /= d2
		c += 1
	c2 = Decimal(2 ** c)
	ak /= ((af1 * af2) ** p * d2 ** s) ** c2
	bk /= ((bf1 * bf2) ** p * d2 ** s) ** c2
	if (I - K) % 2 == 1:
		ak /= af2
		bk /= bf2
getcontext().prec = 16
if fabs(ak + bk) < 0.001:
	print(0)
else:
	print(ak + bk)


from math import sqrt
(i, k, s) = input().split()
(i, k, s) = (int(i), int(k), int(s))
(x, y) = (sqrt(2), sqrt(3))
(a, b) = input().split()
(a, b) = (float(a), float(b))
if (k - i) % 2 == 0:
	print(2 ** (2 * k - 2 * i - s) * (a + b))
else:
	(a, b) = (x * (a + b) - x * y * (a - b), x * (a - b) + x * y * (a + b))
	i = i + 1
	print(2 ** (2 * k - 2 * i - s) * (a + b))


def main():
	h = list(map(int, input().split()))
	i = h[0]
	k = h[1]
	s = h[2]
	h = list(map(int, input().split()))
	a = h[0]
	b = h[1]
	if k >= i:
		x = k - i
		if x % 2 == 0:
			ans = float(a + b) / float(2 ** (s - 2 * x))
			print(ans)
		else:
			ans = float(2 ** 0.5 * (3 ** 0.5 - 1) * ((2 + 3 ** 0.5) * (a + b) + (b - a))) / float(2 ** (s - 2 * x + 2))
			print(ans)
	else:
		x = i - k
		if x % 2 == 0:
			ans = float(a + b) / float(2 ** (s + 2 * x))
			print(ans)
		else:
			ans = float(2 ** 0.5 * (3 ** 0.5 - 1) * ((2 + 3 ** 0.5) * (a + b) + (b - a))) / float(2 ** (s + 2 * x + 2))
			print(ans)
	return 0
main()


import math
(i, k, s) = map(int, input().split())
(ai, bi) = map(int, input().split())
d = abs(k - i)
if k > i:
	if d % 2 == 0:
		t = 2 ** (2 * d - s)
		sk = (ai + bi) * t
	else:
		t = 2 ** (4 * (d // 2) - s)
		ani = math.sqrt(2) * (ai + bi) - math.sqrt(6) * (ai - bi)
		bni = math.sqrt(2) * (ai - bi) + math.sqrt(6) * (ai + bi)
		sk = (ani + bni) * t
elif k < i:
	if d % 2 == 0:
		t = 2 ** (2 * d + s)
		sk = (ai + bi) / t
	else:
		t = 2 ** (4 * ((d + 1) // 2) + s)
		ani = math.sqrt(2) * (ai + bi) - math.sqrt(6) * (ai - bi)
		bni = math.sqrt(2) * (ai - bi) + math.sqrt(6) * (ai + bi)
		sk = (ani + bni) / t
else:
	sk = (ai + bi) / 2 ** s
print('%.3f' % sk)


import math

def func(n, ai, bi, s):
	if n % 2 == 0:
		if 2 * n - s >= 0:
			o = 1 << 2 * n - s
		else:
			o = pow(2, 2 * n - s)
		return o * ai + o * bi
	else:
		if 2 * (n - 1) - s >= 0:
			o = 1 << 2 * (n - 1) - s
		else:
			o = pow(2, 2 * (n - 1) - s)
		return o * ai * 2 * math.sqrt(2) + o * bi * 2 * math.sqrt(6)

def func2(n, ai, bi, s):
	if n % 2 == 0:
		o = pow(2, 2 * n - s)
		return o * ai + o * bi
	else:
		if 2 * (n - 1) - s >= 0:
			o = 1 << 2 * (n - 1) - s
		else:
			o = pow(2, 2 * (n - 1) - s)
		return o * ai * 2 * math.sqrt(2) + o * bi * 2 * math.sqrt(6)
(i, k, s) = list(map(int, input().split()))
(ai, bi) = list(map(int, input().split()))
if i == k:
	print((ai + bi) / pow(2, s))
elif i < k:
	print(func(k - i, ai, bi, s))
else:
	print(func2(k - i, ai, bi, s))


from math import sqrt
s1 = input()
l1 = s1.split()
(i, k, s) = (int(l1[0]), int(l1[1]), int(l1[2]))
l2 = input().split()
(ai, bi) = (int(l2[0]), int(l2[1]))
if k == i:
	print((ai + bi) / 2 ** s)
elif (k - i) % 2 == 0:
	print(2 ** (2 * (k - i) - s) * (ai + bi))
else:
	print(2 ** (2 * (k - i - 1) - s) * (ai * (sqrt(2) * 2) + bi * 2 * sqrt(6)))


from math import floor
(i, k, s) = [int(i) for i in input().split()]
(ai, bi) = [int(i) for i in input().split()]
d = k - i
twos = 4 * floor(d / 2) - s
q = 2 ** twos * (ai + bi)
if d % 2 == 1:
	aj = 2 ** 0.5 * (ai + bi) - 6 ** 0.5 * (ai - bi)
	bj = 2 ** 0.5 * (ai - bi) + 6 ** 0.5 * (ai + bi)
	r = (aj + bj) / (ai + bi)
	q *= r
print(q)


import math
ans = [[0 for x in range(2)] for x in range(2)]
inp = list(map(int, input().split()))
i = inp[0]
k = inp[1]
s = inp[2]
power = i + k - 2
inp = list(map(int, input().split()))
ai = inp[0]
bi = inp[1]
if power % 2 == 0:
	ans[0][0] = pow(2, 2 * power - s - 4 * (i - 1))
	ans[0][1] = 0
	ans[1][0] = 0
	ans[1][1] = pow(2, 2 * power - s - 4 * (i - 1))
else:
	ans[0][0] = pow(2, (power - 1) * 2 - s - 4 * (i - 1)) * (math.sqrt(2) - math.sqrt(6))
	ans[0][1] = pow(2, (power - 1) * 2 - s - 4 * (i - 1)) * (math.sqrt(2) + math.sqrt(6))
	ans[1][0] = pow(2, (power - 1) * 2 - s - 4 * (i - 1)) * (math.sqrt(2) + math.sqrt(6))
	ans[1][1] = pow(2, (power - 1) * 2 - s - 4 * (i - 1)) * (math.sqrt(6) - math.sqrt(2))
ak = ans[0][0] * ai + ans[0][1] * bi
bk = ans[1][0] * ai + ans[1][1] * bi
calc = ak + bk
print(calc)


x = pow(2, 0.5)
y = pow(3, 0.5)
(i, k, s) = [int(h) for h in input().split()]
(a, b) = [int(h) for h in input().split()]
a = a
b = b
if i == k:
	c = (a + b) / pow(2, s)
elif i < k:
	a1 = x * (a + b) - x * y * (a - b)
	b1 = x * (a - b) + x * y * (a + b)
	if (k - i) % 2 == 1:
		l = 2 * (k - i - 1) - s
		c = (a1 + b1) * pow(2, l)
	else:
		l = 2 * (k - i) - s
		c = (a + b) * pow(2, l)
else:
	d = 2 * x * (1 + y * y)
	a1 = (a * (1 - y) + b * (1 + y)) / d
	b1 = (a * (1 + y) + b * (y - 1)) / d
	if (i - k) % 2 == 1:
		l = 2 * (k - i + 1) - s
		c = (a1 + b1) * pow(2, l)
	else:
		l = 2 * (k - i) - s
		c = (a + b) * pow(2, l)
print(c * 1.0)


def multiply22(x, y):
	return [[x[0][0] * y[0][0] + x[0][1] * y[1][0], x[0][0] * y[0][1] + x[0][1] * y[1][1]], [x[1][0] * y[0][0] + x[1][1] * y[1][0], x[1][0] * y[0][1] + x[1][1] * y[1][1]]]

def multiply21(x, y):
	return [[x[0][0] * y[0][0] + x[0][1] * y[1][0]], [x[1][0] * y[0][0] + x[1][1] * y[1][0]]]

def wpower(value, power):
	if power & 1 == 0:
		return ([[1, 0], [0, 1]], 2 * power)
	return (value, 2 * (power - 1))
fw = [[-1.0352761804100832, 3.8637033051562737], [3.8637033051562737, 1.0352761804100832]]
bw = [[-0.06470476127563018, 0.24148145657226705], [0.24148145657226705, 0.06470476127563018]]
(i, k, s) = map(int, input().split())
(ai, bi) = map(int, input().split())
if i == k:
	print((ai + bi) / 2 ** s)
else:
	mat = wpower(fw, k - i)
	ans = multiply21(mat[0], [[ai], [bi]])
	s -= mat[1]
	print((ans[0][0] + ans[1][0]) / 2 ** s)


from decimal import *
getcontext().prec = 150

class Num:
	val = Decimal('0')
	power = 0
	eps = Decimal(10 ** (-15))
	base = 1000
	low = Decimal(1)
	high = Decimal(2 ** 40)
	two = Decimal(2)

	def __init__(self):
		self.val = Decimal('0')
		self.power = 0

	def __init__(self, val, power):
		self.val = val
		self.power = power
		self.sift()

	def sift(self):
		if abs(self.val) == 0:
			self.val = Decimal('0')
			self.power = 0
			return
		negativeFlag = False
		if self.val < 0:
			negativeFlag = True
		self.val = abs(self.val)
		if self.val < self.low:
			start = -1
			end = self.base + 10
			while end - start > 1:
				mid = (end + start) // 2
				if self.val * pow(self.two, mid) < self.low:
					start = mid
				else:
					end = mid
			self.val *= pow(self.two, end)
			self.power -= end
		elif self.val > self.high:
			start = -1
			end = self.base + 10
			while end - start > 1:
				mid = (end + start) // 2
				if self.val / pow(self.two, mid) <= self.high:
					end = mid
				else:
					start = mid
			self.val /= pow(self.two, end)
			self.power += end
		if negativeFlag:
			self.val = -self.val

	def add(self, X):
		ret = Num(Decimal(0), 0)
		if X.val == 0:
			ret.val = self.val
			ret.power = self.power
			return ret
		if self.val == 0:
			ret.val = X.val
			ret.power = X.power
			return ret
		power1 = self.power - min(self.power, X.power)
		power2 = X.power - min(self.power, X.power)
		if power1 >= self.base:
			ret.val = self.val
			ret.power = self.power
			return ret
		if power2 >= self.base:
			ret.val = X.val
			ret.power = X.power
			return ret
		ret.val = self.val * pow(self.two, power1) + X.val * pow(self.two, power2)
		ret.power = min(self.power, X.power)
		ret.sift()
		return ret

	def mul(self, X):
		ret = Num(Decimal(0), 0)
		ret.val = self.val * X.val
		ret.power = self.power + X.power
		ret.sift()
		return ret
C = [[0, 0], [0, 0]]
A = [[0, 0], [0, 0]]
B = [[0, 0], [0, 0]]
X = [[0, 0], [0, 0]]

def mul():
	for i in range(2):
		for j in range(2):
			C[i][j] = 'a'
	for i in range(2):
		for j in range(2):
			for k in range(2):
				if C[i][j] == 'a':
					C[i][j] = A[i][k].mul(B[k][j])
				else:
					C[i][j] = C[i][j].add(A[i][k].mul(B[k][j]))

def getPow(x, y):
	if y == 0:
		return 1
	ans = getPow(x, y // 2)
	ans = ans * ans
	if y % 2 == 1:
		ans = ans * x
	return ans

def power(index):
	if index == 0:
		for i in range(2):
			for j in range(2):
				C[i][j] = Num(Decimal(0), 0)
			C[i][i] = Num(Decimal(1), 0)
		return
	power(index // 2)
	for i in range(2):
		for j in range(2):
			A[i][j] = C[i][j]
			B[i][j] = C[i][j]
	mul()
	if index % 2 == 1:
		for i in range(2):
			for j in range(2):
				A[i][j] = C[i][j]
				B[i][j] = X[i][j]
		mul()
sqrtTwo = Decimal(2).sqrt()
sqrtSix = Decimal(6).sqrt()
X = sqrtTwo - sqrtSix
Y = sqrtTwo + sqrtSix
(a, d) = (sqrtTwo + sqrtSix, -sqrtTwo - sqrtSix)
(b, c) = (sqrtTwo - sqrtSix, sqrtTwo - sqrtSix)
det = a * d - b * c
M = [[Num(a, 0), Num(b, 0)], [Num(c, 0), Num(d, 0)]]
Mi = [[Num(d / det, 0), Num(-b / det, 0)], [Num(-c / det, 0), Num(a / det, 0)]]
(ind1, ind2, s) = map(int, input().split())
(x, y) = map(int, input().split())
(x, y) = (Num(Decimal(x + y), -s), Num(Decimal(x - y), -s))
if ind1 <= ind2:
	X = M
else:
	X = Mi
power(abs(ind1 - ind2))
ans = x.mul(C[0][0])
ans = ans.add(y.mul(C[0][1]))
q = ans.val * pow(Decimal(2), ans.power)
s = str('%.19f' % q)
Z = '-0123456789.'
valid = False
for item in s:
	if item not in Z:
		while True:
			continue
	if item != '0' and item != '.':
		valid = True
if not valid:
	while True:
		continue
print(s)


from decimal import *
(i, k, s) = (1, 1, 5)
(ai, bi) = (4, 5)
(i, k, s) = map(int, input().split())
(ai, bi) = map(int, input().split())
BIG = 1000000000000000000000000000000000000000000
if (k - i) % 2 == 1:
	i += 1
	oai = ai
	obi = bi
	x = Decimal('1.4142135623730950488016887242096980785696718753769480731766797379907324784621070') * BIG
	y = Decimal('2.4494897427831780981972840747058913919659474806566701284326925672509603774573150') * BIG
	ai = int(x * (oai + obi) - y * (oai - obi))
	bi = int(x * (oai - obi) + y * (oai + obi))
else:
	ai = int(ai * BIG)
	bi = int(bi * BIG)
e = (k - i) * 2 - s
s = ai + bi
if e > 0:
	s <<= e
else:
	s >>= -e
print(s / BIG)


import math
from decimal import Decimal
import sys
x = math.sqrt(6) - math.sqrt(2)
y = math.sqrt(6) + math.sqrt(2)

def work(i, k, a, b, s):
	d = k - i
	n2 = int(d / 2) * 4
	if d < 0:
		n2 = int((d - 1) / 2) * 4
	n2 -= s
	s2 = 1
	for i in range(0, abs(n2)):
		s2 *= 2
	if n2 < 0:
		s2 = Decimal(1.0 / float(s2))
	s2 = Decimal(s2)
	if d % 2 == 1:
		a2 = Decimal(float(b) * y - float(a) * x)
		b2 = Decimal(float(a) * y + float(b) * x)
	else:
		a2 = Decimal(float(a))
		b2 = Decimal(float(b))
	ans = Decimal((a2 + b2) * s2)
	return ans
inp = input().split()
i = int(inp[0])
k = int(inp[1])
s = int(inp[2])
inp = input().split()
a = int(inp[0])
b = int(inp[1])
print(work(i, k, a, b, s))


import math
y = 3 ** 0.5
(i, k, s) = map(int, input().split())
(a_i, b_i) = map(int, input().split())
if k > i:
	c = k - i
	exp = c // 2
	if c % 2 == 0:
		e = 2 * c - s
		q = 2 ** e * (a_i + b_i)
	else:
		e = 3 * exp + c / 2 - s
		q = 2 ** e * (a_i + b_i - y * (a_i - b_i) + (a_i - b_i + y * (a_i + b_i)))
elif k < i:
	c = i - k
	exp = c // 2
	if c % 2 == 0:
		e = -(2 * c) - s
		q = (a_i + b_i) * 2 ** e
	else:
		e = 3 * exp - c / 2 - 3 * c - s
		q = ((1 - y) * a_i + (1 + y) * b_i + ((1 + y) * a_i + (y - 1) * b_i)) * 2 ** e
else:
	q = 2 ** (math.log2(a_i + b_i) - s)
print(q)