Read problems statements [Hindi] , [Vietnamese] , [Mandarin Chinese] , [Russian] and [Bengali] as well.

The last time in Byteland, Chef defeated the magician in his challenge and won a gold coin.

The magician does not want to give up his coin so easily, so he gives Chef $N$ coins. One of them is real and the remaining $N-1$ are fake; all fake coins have equal weights, different from the weight of the real coin. The coins are otherwise indistinguishable.

Chef has to find the real coin by himself. To make it fair, the magician gives Chef a balance. The balance is magical — it stays balanced when the sums of weights of coins put on each side are equal, but if they are not equal, the balance tilts to a random side instead of the side with the greater sum of weights. Chef can only use this balance up to $K$ times; if he cannot uniquely determine which coin is the real one afterwards, he has to guess the real coin (he may make a guess in any way he wants).

If Chef uses the balance optimally, what is the minimum possible probability that he will correctly determine the real coin at the end? We are interested in the worst-case scenario where the position of the gold coin is fixed initially (but unknown to Chef).

------  Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first and only line of each test case contains two space-separated integers $N$ and $K$.

------  Output ------
For each test case, print a single line containing one integer — the minimum probability that Chef will find the gold coin. Your output will be considered correct if its absolute error does not exceed $ 10^{-6}$.

------  Constraints  ------
$1 ≤ T ≤ 2 \cdot 10^{5}$
$1 ≤ N ≤ 10^{18}$
$0 ≤ K ≤ 10^{9}$

------  Subtasks ------
Subtask #1 (25 points): $1 ≤ N ≤ 10^{5}$

Subtask #2 (75 points): original constraints

----- Sample Input 1 ------ 
4
3 1
3 2
4 1
1 5
----- Sample Output 1 ------ 
0.500000
1.000000
0.500000
1.000000
----- explanation 1 ------ 
Example case 1: Chef takes two coins and puts them on the two sides of the balance. If the balance tilts, then one of these two coins is real. (Otherwise, they are both fake and Chef found the real coin; we do not consider this scenario, since it does not lead to the minimum probability.) Chef cannot use the balance any more, so he cannot determine which of these two coins is the real one. He has to guess one; this guess is correct with probability $1/2$.

Example case 2: The first use of the balance is the same as before. If the balance does not tilt, he knows the real coin. Otherwise, Chef replaces one coin on the balance. If the balance tilts again, the coin that was not replaced is the real one. Otherwise, the replaced coin is the real one.

Difficulty: HARD
Tags: Constructive algorithms

Ad-hoc

Mathematics

Probability

Starter code:

Solutions:
def f(N, K):
	if N == 1:
		return 1.0
	if N == 2:
		return 0.5
	for i in range(K):
		if N == 1:
			break
		if N == 2:
			N = 1
		if i == 0:
			if N % 4 == 0:
				N //= 2
			else:
				N = N // 2 + 1
		elif N % 2 == 0:
			N //= 2
		else:
			N = N // 2 + 1
	return 1.0 / N
T = int(input())
for _ in range(T):
	(N, K) = (int(x) for x in input().split())
	print(f(N, K))


def compute(n, k, spare):
	if k == 0:
		return 1 / n
	if n == 1:
		return 1
	if n == 2:
		if spare:
			return 1
		else:
			return 1 / 2
	next_n = 0
	if n % 4 == 0:
		next_n = n // 2
	elif n % 4 == 1:
		next_n = n // 2 + 1
	elif n % 4 == 2:
		if spare:
			next_n = n // 2
		else:
			next_n = n // 2 + 1
	else:
		next_n = n // 2 + 1
	return compute(next_n, k - 1, True)
T = int(input())
for _ in range(T):
	(N, K) = (int(i) for i in input().split())
	print(compute(N, K, False))


def calc(n, k):
	if k >= n:
		return 1
	if k == 0:
		return 1 / n
	hf1 = n // 2
	hf2 = n - hf1
	return calc(max(hf1, hf2), k - 1)
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	if n == 1:
		print(1)
	elif n == 2:
		print(0.5)
	elif k == 1:
		hf1 = n // 2
		hf2 = n - hf1
		if hf1 & 1 and hf2 & 1:
			print(1 / (max(hf1, hf2) + 1))
		else:
			print(1 / max(hf1, hf2))
	else:
		print(calc(n, k))


import decimal

def solve(n, r, s):
	if s == 0:
		return r
	else:
		if r == 1:
			return 1
		if r == 2:
			if n > 2:
				return 1
			else:
				return 2
		elif r % 2 == 1:
			return solve(n, r // 2 + 1, s - 1)
		else:
			a = r // 2
			if r == n:
				if a % 2 == 1:
					return solve(n, a + 1, s - 1)
				else:
					return solve(n, a, s - 1)
			else:
				return solve(n, a, s - 1)
for i in range(int(input())):
	(n, k) = map(int, input().split())
	print(decimal.Decimal(1) / decimal.Decimal(solve(n, n, k)))


import math
t = int(input())
for x in range(t):
	(n, k) = map(int, input().split())
	if n == 1:
		print(str.format('{0:.6f}', 1))
		continue
	if k == 0:
		print(str.format('{0:.6f}', 1 / n))
		continue
	if n == 2:
		print(str.format('{0:.6f}', 1 / 2))
		continue
	l = math.ceil(math.log2(n))
	if k >= l:
		print(str.format('{0:.6f}', 1))
		continue
	elif k == 1:
		a = math.ceil(n / 2)
		if a % 2 == 1:
			if a + a == n:
				a = a + 1
		print(str.format('{0:.6f}', 1 / a))
		continue
	else:
		m = math.ceil(n / 2 ** k)
		print(str.format('{0:.6f}', 1 / m))


import sys
for (n, k) in [map(int, line.split(' ')) for line in sys.stdin.read().split('\n')[1:] if line]:
	if n > 2 and k > 0:
		(n, k) = (n // 2 + int(n % 4 != 0), k - 1)
		n = (n - 1 >> min(k, 60)) + 1
	print('%.10f' % (1.0 / n))


import math as m
for etc in range(int(input())):
	(n, k) = map(int, input().split())
	if n == 2:
		print(1 / 2)
		continue
	if n > 2 and k:
		n = (n >> 1) + bool(n & 3)
		k -= 1
	while n > 1 and k > 0:
		n = n + 1 >> 1
		k -= 1
	print(1 / n)


for _ in range(int(input())):
	(N, K) = map(int, input().split())
	if N == 2:
		print('%.6f' % 0.5)
	else:
		if K >= 1:
			if N % 2 == 1:
				N = N // 2 + 1
			elif N % 4 == 0:
				N = N // 2
			else:
				N = N // 2 + 1
			for i in range(1, K):
				if N > 1:
					N = N // 2 + N % 2
				else:
					break
		print('%.10f' % float(1.0 / N))


from math import ceil

def fun(n, k):
	if n == 1 or n == 2:
		print(1 / n)
	else:
		if k > 0 and n % 4 == 2:
			n = n // 2 + 1
			k = k - 1
		k = min(k, 70)
		x = pow(2, k)
		ans = n / x
		ans = ceil(ans)
		print(1 / ans)

def t():
	test = int(input())
	for t in range(test):
		(n, k) = map(int, input().split())
		fun(n, k)
t()


t = int(input())
for _ in range(t):
	ln = input()
	tn = int(ln.split()[0])
	k = int(ln.split()[1])
	if tn == 1:
		print(1)
		continue
	if tn == 2:
		print(0.5)
		continue
	n = tn
	while n > 1 and k > 0:
		k -= 1
		if n == tn and n // 2 % 2 == 1 and (n % 2 == 0):
			n = n // 2 + 1
		else:
			n = n // 2 + n % 2
	print(1.0 / n)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	clear = 0
	temp = 0
	run = n
	if n == 1:
		print('{0:.7f}'.format(1.0))
	elif n == 2:
		print('{0:.7f}'.format(0.5))
	else:
		if run == 3 and k > 0:
			run = 2
			k -= 1
		while k > 0:
			if run < 2:
				break
			xx = run // 2
			if run & 1:
				(clear, run) = (xx, xx + 1)
				k -= 1
			elif xx & 1:
				if xx > 1:
					if clear >= xx:
						clear = xx
						run = xx + temp
						temp = 0
						k -= 1
					else:
						run = xx + 1 + temp
						clear = xx + 1
						temp = 0
						k -= 1
				else:
					run = 1 + temp
					temp = 0
					k -= 1
			else:
				clear = xx
				run = xx + temp
				temp = 0
				k -= 1
		if k == 0:
			print('{0:.7f}'.format(1.0 / run))
		else:
			print('{0:.7f}'.format(1.0))


def getminp(n, k):
	if n == 1:
		return 1.0
	if n == 2:
		return 0.5
	looped = False
	while k:
		if n == 1 or n == 2:
			return 1
		if n % 4 == 0:
			n //= 2
		elif n % 2 == 0 and looped:
			n = n // 2
		else:
			n = n // 2 + 1
		k -= 1
		looped = True
	return 1 / n
for _ in range(int(input())):
	i = list(map(int, input().split()))
	print(str.format('{0:.6f}', getminp(i[0], i[1])))


import math
t = int(input())
while t > 0:
	t -= 1
	(n, k) = input().split()
	n = int(n)
	k = int(k)
	if k == 0:
		print('%.20f' % (1 / n))
	elif n == 2:
		print('%.20f' % (1 / 2))
	elif n == 1:
		print('%.20f' % 1)
	else:
		x = 0
		if n % 2 == 0:
			if n / 2 % 2 == 1:
				n = n / 2 + 1
			else:
				n = n / 2
		else:
			n = math.ceil(n / 2)
		k -= 1
		while k > 0:
			if n < 2:
				break
			n = math.ceil(n / 2)
			k -= 1
		print('%.20f' % (1 / n))


def hell(n, k):
	if n == 0:
		return 1
	if k == 0 or n == 1:
		return n
	val = int(n / 2)
	if n % 2:
		val += 1
	return hell(val, k - 1)
for _ in range(int(input())):
	i = list(map(int, input().split()))
	if i[0] % 2 == 0 and i[1] == 1 and (i[0] / 2 % 2 != 0):
		a = 1 / (int(i[0] / 2) + 1)
	elif i[0] > 2:
		a = 1 / hell(i[0], i[1])
	else:
		a = 1 / i[0]
	print(str.format('{0:.6f}', a))


def main():
	t = int(input())
	for i in range(t):
		s = input().split()
		n = int(s[0])
		k = int(s[1])
		if n == 1:
			print('1.000000')
		elif n == 2:
			print('0.500000')
		elif k > 64:
			print('1.000000')
		elif k == 1:
			if n % 2 == 1:
				n = int(n / 2) + 1
			else:
				n = int(n / 2)
				if n % 2 != 0:
					n = n + 1
			print('%.6f' % (1 / n))
		else:
			for i in range(k):
				if n == 1:
					break
				n = max(int(n / 2), int((n + 1) / 2))
			print('%.6f' % (1 / n))
main()


import math
t = int(input())
while t > 0:
	(n, k) = map(int, input().split())
	if n > 2:
		if k != 1:
			var = math.log(n, 2)
			if k >= var:
				print('1')
			else:
				for i in range(k):
					n = math.ceil(n / 2)
				print(1 / n)
		else:
			if n % 2 != 0:
				n = 1 + n // 2
			elif n // 2 % 2 == 0:
				n = n // 2
			else:
				n = n // 2 + 1
			print(1 / n)
	else:
		a = [0, 1, 0.5]
		print(a[n])
	t -= 1


import math
t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	if n == 1 or n == 2:
		n = n
	elif k == 1:
		if n % 2 == 0:
			if n // 2 % 2 == 0:
				n = n / 2
			else:
				n = n / 2 + 1
		else:
			n = n // 2 + 1
	elif k >= math.log(n, 2):
		n = 1
	else:
		j = 0
		while j < k:
			if n % 2 == 0:
				n = n / 2
			else:
				n = n // 2 + 1
			j = j + 1
	print('{0:.7f}'.format(1 / n))


def yoyo(n, k):
	check = 0
	while True:
		if n & 1:
			n = n // 2 + 1
		else:
			n = n // 2
		check += 1
		if check == k:
			break
		if n <= 1:
			break
	if check == k:
		p = 1 / n
		print(p)
	else:
		print(1)

def deep_is_back():
	t = int(input())
	for it in range(t):
		(n, k) = map(int, input().split())
		if k == 0:
			x = 1 / n
			print(x)
		elif n == 1:
			print(1)
		elif n == 2:
			print(0.5)
		elif k == 1:
			if n % 2 == 1:
				x = n // 2 + 1
				p = 1 / x
				print(p)
			elif n % 2 == 0 and n // 2 % 2 == 0:
				x = n // 2
				p = 1 / x
				print(p)
			elif n % 2 == 0 and n // 2 % 2 == 1:
				x = n // 2 + 1
				p = 1 / x
				print(p)
		else:
			yoyo(n, k)
deep_is_back()


from math import ceil

def chek(number_of_coin, k_balance):
	if k_balance == 0:
		print('{0:.6f}'.format(1 / number_of_coin))
	elif number_of_coin == 1:
		print('{0:.6f}'.format(1))
	elif number_of_coin == 2:
		print('{0:.6f}'.format(1 / 2))
	else:
		if k_balance > 0 and number_of_coin % 2 == 0 and (int(number_of_coin / 2) % 2 != 0):
			number_of_coin = ceil(number_of_coin / 2) + 1
			k_balance -= 1
		while k_balance > 0 and number_of_coin > 1:
			number_of_coin = ceil(number_of_coin / 2)
			k_balance -= 1
		if k_balance == 0:
			print('{0:.6f}'.format(1 / number_of_coin))
		elif number_of_coin == 1:
			print('{0:.6f}'.format(1))
for _ in range(int(input())):
	(number_of_coin, k_balance) = [int(x) for x in input().split()]
	chek(number_of_coin, k_balance)


def f1(n):
	print(n, ':')
	if n < 3:
		print('{0:.6f}'.format(1 / n))
		return None
	k = 0
	print(k, ':', '{0:.6f}'.format(1 / n), ';', n)
	k += 1
	n = n // 4 * 2 + min(n % 4, 2)
	while n > 1:
		print(k, ':', '{0:.6f}'.format(1 / n), ';', n)
		n = n // 2 + n % 2
		k += 1
	if n == 1 and k > 0:
		print(k, ':', '{0:.6f}'.format(1 / n))
	else:
		print('error')
	return None

def f(n, k):
	if n < 3:
		return n
	if k > 0:
		n = n // 4 * 2 + min(n % 4, 2)
		k -= 1
	while k > 0 and n > 1:
		n = n // 2 + n % 2
		k -= 1
	return n
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	print('{0:.6f}'.format(1 / f(n, k)))


import math
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	if n == 2:
		print(0.5)
	elif n == 1 and k > 0:
		print(1.0)
	else:
		t = k
		if k > 72 or 2 ** k >= n:
			print(1.0)
		else:
			while n > 2 and k > 0:
				if t == k and n % 4 == 2:
					n = max(2 * math.ceil(n / 4), n - 2 * math.ceil(n / 4))
					k -= 1
				else:
					n = max(math.ceil(n / 2), n - math.ceil(n / 2))
					k -= 1
			if k == 0:
				print(1 / n)
			elif n == 2 and k > 0:
				print(1.0)


import math as m

def main(n, k):
	if k == 0:
		return 1 / n
	if n == 1:
		return 1.0
	if n == 2 and k >= 1 or (n == 3 and k > 1):
		return 1.0
	else:
		num1 = n // 2
		num2 = n - num1
		return main(max(num1, num2), k - 1)
t = int(input())
for i in range(0, t):
	n_k = input().split(' ')
	n = int(n_k[0])
	k = int(n_k[1])
	if k == 0:
		print(str.format('{0:.7f}', 1 / n)[:8])
	elif n == 2:
		print('0.500000')
	elif n == 3 and k == 2:
		print(str.format('{0:.7f}', 1)[:8])
	else:
		num1 = n // 2
		if num1 % 2 == 0:
			num2 = n - num1
		if num1 % 2 != 0 and n % 2 != 0:
			num2 = n - num1
		elif num1 % 2 != 0 and n % 2 == 0:
			num1 = num1 - 1
			num2 = n - num1
		print(str.format('{0:.7f}', main(max(num1, num2), k - 1))[:8])


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	if k == 0 or n <= 2:
		print(1 / n)
	else:
		k -= 1
		if n & 1:
			n = n + 1 >> 1
		elif n & 2:
			n = n + 2 >> 1
		else:
			n = n >> 1
		while n >= 2 and k > 0:
			k -= 1
			n = n + 1 >> 1
		print(1 / n)


def paradox2(vb1, vb2, vb3):
	if vb1 <= 1:
		return 1
	if vb2 == 0:
		return 1 / vb1
	LF = 0
	if vb3 > 0 or vb1 % 2 != 0:
		LF = (vb1 + 1) // 2
	else:
		HF = vb1 // 2
		if HF % 2 == 0:
			LF = HF
		else:
			LF = HF + 1
	return paradox(LF, vb2 - 1, vb3 + vb1 - LF)

def paradox(vb1, vb2):
	vb3 = 0
	while True:
		if vb1 <= 1:
			return 1
		if vb2 == 0:
			return 1 / vb1
		LF = 0
		if vb3 > 0 or vb1 % 2 != 0:
			LF = (vb1 + 1) // 2
		else:
			HF = vb1 // 2
			if HF % 2 == 0:
				LF = HF
			else:
				LF = HF + 1
		vb3 += vb1 - LF
		vb1 = LF
		vb2 -= 1
subho = []
TC = int(input())
for ti in range(TC):
	(VM1, VM2) = map(int, input().split())
	subho.append(paradox(VM1, VM2))
print('\n'.join(map(str, subho)))


import math
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	p = k
	if n == 1 or n == 2:
		pass
	else:
		while k:
			if n == 2:
				n = 1
				break
			if n % 2 == 0:
				n = n // 2
				if n % 2 == 1 and p == k:
					n += 1
			else:
				n = math.ceil(n / 2)
			k -= 1
	print('%.6f' % (1 / n))


import math

def chk(n):
	if n % 2 == 1:
		return math.floor(n / 2) + 1
	elif n / 2 % 2 == 0:
		return n / 2
	else:
		return n / 2

def main():
	t = int(input())
	while t > 0:
		a = [int(x) for x in input().split()]
		n = a[0]
		k = a[1]
		if n == 1:
			print('%.10f' % 1.0)
		elif n == 2:
			print('%.10f' % 0.5)
		elif k == 0:
			print('%.10f' % (1.0 / n))
		else:
			k = k - 1
			if n % 2 == 1:
				n = math.floor(n / 2) + 1
			elif n / 2 % 2 == 0:
				n = n / 2
			else:
				n = n / 2 + 1
			while k > 0:
				k = k - 1
				if n == 2:
					n = 1
					break
				s = chk(n)
				n = s
			print('%.10f' % (1.0 / n))
		t = t - 1
main()


import math
t = int(input())
ans = {}
for i in range(t):
	(n, k) = map(int, input().split())
	if n == 2:
		ans[i] = 1.0 / 2
		continue
	elif k == 1 and n // 2 % 2 == 0:
		n = math.ceil(n / 2)
	elif k == 1 and n // 2 % 2 != 0:
		n = n // 2 + 1
	else:
		while n > 1 and k > 0:
			n = math.ceil(n / 2)
			k -= 1
	prob = 1.0 / n
	ans[i] = prob
for i in ans:
	print(ans[i])


import math
t = int(input())
ans = []
for i in range(t):
	(n, k) = map(int, input().split())
	if k == 0:
		n = n
	elif n == 2:
		n = 2
	elif k == 1 and n // 2 % 2 == 0:
		x1 = n // 2
		x2 = n - x1
		n = max(x1, x2)
	elif k == 1 and n // 2 % 2 != 0:
		n = n // 2 + 1
	else:
		while n > 1 and k > 0:
			n = math.ceil(n / 2)
			k -= 1
	prob = 1.0 / n
	ans.append(prob)
for i in ans:
	print(i)


import math
t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	if k == 0:
		n = n
	elif n == 2:
		n = 2
	elif k > n // 2 or n == 1:
		n = 1.0
	elif k == 1 and n // 2 % 2 == 0:
		x1 = n // 2
		x2 = n - x1
		n = max(x1, x2)
	elif k == 1 and n // 2 % 2 != 0:
		n = n // 2 + 1
	else:
		while k > 0 and n > 1:
			n = math.ceil(n / 2)
			k -= 1
	prob = 1.0 / n
	print('{0:.6f}'.format(prob))


t = int(input())
for t in range(t, 0, -1):
	(n, k) = map(int, input().split())
	if k == 0:
		print(format(1 / n, '.8f'))
		continue
	if n == 1:
		print(1)
		continue
	if n == 2:
		print(format(1 / 2, '.8f'))
		continue
	if k >= 100:
		print(1)
		continue
	if k > 1:
		if n <= 2 ** k:
			print(1)
			continue
	if n % 2 == 0:
		if n // 2 % 2 != 0 and (n - n // 2) % 2 != 0:
			n = n // 2 + 1
			k = k - 1
	for k in range(k, 0, -1):
		if n % 2 == 0:
			n = n // 2
		else:
			n = n // 2 + 1
	print(format(1 / n, '.8f'))


(_, __, ________) = (1, 2, 0)

def odd(___):
	return ___ % __ == _

def solve(___, ____, _____):
	if _____ == ________:
		return ____
	else:
		if ____ == _:
			return _
		if ____ == __:
			return _ if ___ > __ else __
		elif odd(____):
			return solve(___, ____ // __ + _, _____ - _)
		else:
			______ = ____ // __
			return solve(___, ______ + _, _____ - _) if ____ == ___ and odd(______) else solve(___, ______, _____ - _)
for _________ in range(int(input())):
	(___, _______) = map(int, input().split())
	print(_ / solve(___, ___, _______))


def solve(N, K):
	if K == 0:
		return 1 / N
	if N == 1:
		return 1.0
	if N == 2:
		return 0.5
	if N % 4 == 0:
		N = N // 2
	elif N % 4 == 1:
		N = N // 2 + 1
	elif N % 4 == 2:
		N = N // 2 + 1
	else:
		N = 2 * (N // 4) + 2
	K -= 1
	while K > 0 and N >= 2:
		N = N // 2 + N % 2
		K -= 1
	if K == 0:
		return 1 / N
	return 1.0
T = int(input())
for i in range(0, T):
	(N, K) = [int(s) for s in input().split(' ') if s != '']
	print('%.6f' % solve(N, K))


for i in range(int(input())):
	(n, k) = map(int, input().split())
	if n == 2:
		print(str.format('{0:.8f}', 1 / 2))
		continue
	if k == 1:
		n1 = n // 2
		n2 = n - n1
		if n1 % 2 == 1 and n2 % 2 == 1:
			n = n1 + 1
		else:
			n = max(n1, n2)
		print(str.format('{0:.8f}', 1 / n))
		continue
	while n > 1 and k > 0:
		n1 = n // 2
		n2 = n - n1
		n = max(n1, n2)
		k -= 1
	print(str.format('{0:.8f}', 1 / n))


import math
cases = int(input())
for case in range(cases):
	(n, k) = [int(i) for i in input().split()]
	if k == 0:
		print(1 / n)
		continue
	if n == 1:
		print(1)
		continue
	elif n == 2:
		print(1 / 2)
		continue
	limit = math.ceil(math.log2(n))
	if k >= limit:
		print(1)
		continue
	elif k == 1:
		den = math.ceil(n / 2)
		if n % 2 == 0 and den % 2 != 0:
			den += 1
		print(1 / den)
		continue
	else:
		den = math.ceil(n / 2 ** k)
		print(1 / den)


from math import ceil, log2
T = int(input())
for _ in range(T):
	(N, K) = map(int, input().split())
	if N == 2:
		print(0.5)
	elif K <= ceil(log2(N)) + 1:
		if N % 4 and (not N % 2) and (K == 1):
			print(1 / ceil((N + 1) / 2 ** K))
		else:
			print(1 / ceil(N / 2 ** K))
	else:
		print(1)


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

	def check(n, k):
		if n == 4 and k >= 2:
			return 1
		if n == 2 or (n == 3 and k == 1):
			return 1 / 2
		if n == 1:
			return 1
		if k == 0:
			return 1 / n
		if n == 3:
			return 1
		if n % 2 == 0:
			return check(n // 2, k - 1)
		return check(n // 2 + 1, k - 1)
	(n, k) = map(int, input().split())
	if k == 0:
		print(1 / n)
	elif k == 1:
		if n == 2 or n == 3 or n == 4:
			print(1 / 2)
		elif n == 1:
			print(1)
		elif n % 4 == 0:
			print(check(n // 2, 0))
		else:
			print(check(n // 2 + 1, 0))
	else:
		print(check(n, k))


T = int(input())
for t in range(T):
	(N, k) = list(map(int, input().split()))
	if N == 1:
		print(float(1))
	elif N == 2:
		print(str(1 / 2))
	else:
		if k >= 1:
			if N % 2 == 0:
				N = N // 2
				if N % 2 == 1:
					N += 1
			else:
				N = (N + 1) // 2
		for i in range(1, k):
			if N % 2 == 0:
				N = N // 2
			else:
				N = (N + 1) // 2
			if N == 1:
				break
		print(str(1 / N))


t = int(input())
while t:
	(n, k) = map(int, input().split())
	flag = True
	result = 0
	while flag:
		x = 0
		if n <= 1:
			flag = False
			print(str.format('{0:.6f}', 1))
		if k == 0 and flag != False:
			flag = False
			print(str.format('{0:.6f}', 1 / n))
		if n % 2 != 0 or result > 0:
			x = (n + 1) // 2
		else:
			mid = n // 2
			if mid % 2 == 0:
				x = mid
			else:
				x = mid + 1
		result = result + n - x
		n = x
		k -= 1
	t -= 1


T = int(input())
for t in range(T):
	(n, k) = map(int, input().split())
	ss = 0
	if n <= 2 or k == 0:
		ss = n
	else:
		if n % 4 == 0:
			ss = n // 2
		else:
			ss = n // 2 + 1
		for i in range(k - 1):
			if ss % 2 == 1:
				ss = ss // 2 + 1
			else:
				ss = ss // 2
			if ss == 1:
				break
	print(1 / ss)


import math
mem = [[-1] * 18 for j in range(100010)]
orn = 0

def pr(n, k):
	global mem
	global orn
	if n == 1:
		return 1
	elif n == 2:
		if orn > 2 and k >= 1:
			return 1
		else:
			return 1 / 2
	elif n == 3 and k >= 2:
		return 1
	elif n == 3 and k == 1:
		return 1 / 2
	elif n == 4 and k >= 2:
		return 1
	elif k <= 0:
		return 1 / n
	else:
		up = math.ceil(math.log2(n))
		if k >= up:
			return 1
		if n % 2 == 0 and n % 4 != 0:
			n1 = int(math.ceil(n / 2)) + 1
			k -= 1
			while k > 0:
				k -= 1
				n1 = int(math.ceil(n1 / 2))
			return 1 / n1
		else:
			n1 = n
			while k > 0:
				k -= 1
				n1 = int(math.ceil(n1 / 2))
			return 1 / n1
t = int(input())
for rr in range(t):
	(n, k) = map(int, input().strip().split(' '))
	orn = n
	print(float(pr(n, k)))


from math import ceil

def solve():
	results = []
	for _ in range(int(input())):
		(N, K) = input().split()
		(N, K) = (int(N), int(K))
		if N == 2 or K == 0:
			results.append(1 / N)
			continue
		coins_left = N
		if K > 2000:
			results.append(1)
			continue
		while coins_left > 1 and K > 0:
			a = ceil(coins_left / 2)
			coins_left -= a
			if coins_left + a == N and a % 2 != 0 and (coins_left % 2 != 0):
				a -= 1
				coins_left += 1
			coins_left = max(a, coins_left)
			K -= 1
		if K == 0 and coins_left > 0:
			results.append(1 / coins_left)
		elif K > 0 or coins_left == 1:
			results.append(1)
	print('\n'.join((str(k) for k in results)))
solve()


def sol():
	(n, k) = map(int, input().split())
	if n == 2 or k == 0:
		return 1 / n
	if n % 2 == 0 and n % 4 != 0:
		n = int(n / 2) + 1
		k -= 1
	while k > 0 and n > 1:
		n = int(n / 2) + n % 2
		k -= 1
	return 1 / n
t = int(input())
for i in range(t):
	print(sol())


I = lambda : map(int, input().split())
for _ in range(int(input())):
	(n, k) = I()
	if n == 1:
		print(1.0)
	elif n == 2:
		print(0.5)
	elif n == 3:
		if k == 1:
			print(1 / 2)
		elif k == 0:
			print(1 / 3)
		else:
			print(1.0)
	else:
		if k == 1:
			k -= 1
			if n % 4 == 0:
				n = n // 2
			else:
				n = n // 2 + 1
		while n > 1 and k != 0:
			n = n - n // 2
			k -= 1
		print(1 / n)


import math
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	if n == 1:
		print(1.0)
	elif n == 2:
		print(0.5)
	elif k == 1 and (n % 2 == 0 and n / 2 % 2 != 0):
		print(1 / (n / 2 + 1))
	else:
		while k > 0:
			n = math.ceil(n / 2)
			if n == 1:
				break
			k = k - 1
		print(1 / n)


def min_chance(n, k):
	if n == 1:
		return 1
	if k == 0:
		return 1 / n
	half = n - n // 2
	return min_chance(half, k - 1)
for _ in range(int(input())):
	(n, k) = [int(x) for x in input().split()]
	if n == 2:
		print(1 / 2)
	elif n == 1:
		print(1.0)
	elif k == 0:
		print(1 / n)
	else:
		if n % 4 == 2:
			half = n // 2 + 1
		else:
			half = n - n // 2
		print(min_chance(half, k - 1))


tc = int(input())
for t in range(tc):
	(n, k) = [int(temp) for temp in input().split()]
	ans = n
	if ans == 2:
		dan = 1 / ans
		print('%.6f' % dan)
		continue
	for i in range(1, k + 1):
		if ans == 1:
			break
		if i == 1:
			if ans % 2 == 0:
				ans = ans // 2
				if ans % 2 != 0:
					ans = ans + 1
			else:
				ans = ans // 2 + 1
		elif ans % 2 == 0:
			ans = ans // 2
		else:
			ans = ans // 2 + 1
	dan = 1 / ans
	print('%.6f' % dan)


def solve2(N1, N2, N3):
	if N1 <= 1:
		return 1
	if N2 == 0:
		return 1 / N1
	left = 0
	if N3 > 0 or N1 % 2 != 0:
		left = (N1 + 1) // 2
	else:
		half = N1 // 2
		if half % 2 == 0:
			left = half
		else:
			left = half + 1
	return solve(left, N2 - 1, N3 + N1 - left)

def solve(N1, N2):
	N3 = 0
	while True:
		if N1 <= 1:
			return 1
		if N2 == 0:
			return 1 / N1
		left = 0
		if N3 > 0 or N1 % 2 != 0:
			left = (N1 + 1) // 2
		else:
			half = N1 // 2
			if half % 2 == 0:
				left = half
			else:
				left = half + 1
		N3 += N1 - left
		N1 = left
		N2 -= 1
res = []
t = int(input())
for ti in range(t):
	(n, k) = map(int, input().split())
	res.append(solve(n, k))
print('\n'.join(map(str, res)))


def solve(num, step):
	out = 0
	while True:
		if num <= 1:
			return 1
		if step == 0:
			return 1 / num
		left = 0
		if out > 0 or num % 2 != 0:
			left = (num + 1) // 2
		else:
			half = num // 2
			if half % 2 == 0:
				left = half
			else:
				left = half + 1
		out += num - left
		num = left
		step -= 1
ans = []
T = int(input())
for ti in range(T):
	(N, K) = map(int, input().split())
	ans.append(solve(N, K))
print('\n'.join(map(str, ans)))


t = int(input())
for var in range(t):
	(n, k) = map(int, input().split())
	count = 0
	res = n
	flag = 0
	if n == 2:
		print('0.5000000')
	elif k == 0:
		print('{0:0.8f}'.format(1 / n))
	else:
		while count < k and res != 1:
			if res % 2 == 0:
				res = int(res / 2)
				if res % 2 == 1 and flag == 0:
					if res != 1:
						res += 1
			elif res % 2 == 1:
				res = int(res / 2)
				res += 1
			flag = 1
			count += 1
		print('{0:0.8f}'.format(1 / res))


def findRealCoin(n, k):
	if n == 2:
		return 1 / 2.0
	if k >= 1:
		div = n // 4
		rem = n % 4
		if rem == 0:
			n = div + div
		if rem == 1:
			n = div + div + 1
		if rem == 2:
			n = div + 1 + div + 1
		if rem == 3:
			n = div + 1 + div + 1
		k -= 1
	while k > 0 and n >= 2:
		n = (n + 1) // 2
		k -= 1
	return float(1 / n)
T = int(input())
for i in range(T):
	(N, K) = list(map(int, input().split()))
	print(findRealCoin(N, K))


t = int(input())
for it in range(t):
	(n, k) = map(int, input().split())
	z = k
	x = n
	if k == 1:
		if x % 2 == 0:
			if x // 2 % 2 == 0:
				x = x // 2
				z -= 1
			else:
				x = x // 2 + 1
				z -= 1
		elif x // 2 % 2 == 0:
			x = x // 2 + 1
			z -= 1
		else:
			x = x // 2 + 1
			z -= 1
		print(1 / x)
		continue
	if x == 2:
		print(0.5)
		continue
	while z != 0 and x > 3:
		if x % 2 == 0:
			if x // 2 % 2 == 0:
				x = x // 2
				z -= 1
			else:
				x = x // 2
				z -= 1
		elif x // 2 % 2 == 0:
			x = x // 2 + 1
			z -= 1
		else:
			x = x // 2 + 1
			z -= 1
	if x == 3:
		if z >= 2:
			print(1)
		elif z == 1:
			print(0.5)
		else:
			print(1 / x)
	elif x == 2:
		if z >= 1:
			print(1)
		elif z == 0:
			print(0.5)
		else:
			print(1 / x)
	elif x == 1:
		print(1)
	elif x > 3 and z == 0:
		print(1 / x)


def fun(n, k):
	if n == 1:
		return 1
	if k == 0:
		return 1 / n
	if k == 1:
		return 1 / (n // 2 + n % 2)
	return fun(n // 2 + n % 2, k - 1)
for _ in range(int(input())):
	(n, k) = [int(i) for i in input().split()]
	use = fun(n, k)
	if n == 2:
		use = 0.5
	if k == 1:
		use = 1 / (n // 2 + n % 2 + n // 2 % 2 * (1 - n % 2))
	print('%.6f' % use)


from math import floor
from math import ceil

def g(n):
	if n % 4 == 0:
		return 2 * floor(n / 4)
	if n % 4 == 1:
		return 2 * floor(n / 4) + 1
	else:
		return 2 * floor(n / 4) + 2

def f(n, k):
	if n == 1:
		return 1
	if n == 2:
		return 0.5
	if k == 0:
		return 1 / n
	n = g(n)
	k = k - 1
	while n > 1 and k > 0:
		n = ceil(n / 2)
		k = k - 1
	return 1 / n
t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	print('{0:.6f}'.format(f(n, k)))


import numpy as np

def max_inv_prob(n, k):
	tot = n
	if n == 1:
		return 1
	if n == 2:
		return 2
	while n > 1 and k > 0:
		if n == 2:
			n = 1
		elif n % 2 == 1:
			n = (n + 1) // 2
		elif n // 2 % 2 == 0 or tot - n >= n // 2:
			n = n // 2
		else:
			n = n // 2 + 1
		k -= 1
	return n
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	p = max_inv_prob(n, k)
	print('%.8f' % (1 / p))


for h in range(int(input())):
	(n, chances) = map(int, input().strip().split())
	flag = 1
	if n == 2:
		print(0.5)
	elif n == 1:
		print(1)
	else:
		while chances:
			if n == 2:
				break
			if n % 2 == 0:
				p = n // 2
				if p % 2 == 1 and flag:
					flag = 0
					n = p + 1
				else:
					n = p
			else:
				n = n // 2 + 1
			chances -= 1
			flag = 0
		if chances > 0:
			print(1)
		else:
			print(1 / n)


def solve_level2(N, K):
	if N == 1 or K == 0:
		return N
	return solve_level2((N + 1) // 2, K - 1)

def solve(N, K):
	if N == 1 or N == 2 or K == 0:
		return N
	if N % 2 == 1:
		return solve_level2((N + 1) // 2, K - 1)
	if N % 4 == 0:
		return solve_level2(N // 2, K - 1)
	return solve_level2(N // 2 + 1, K - 1)
t = int(input())
while t > 0:
	t -= 1
	(N, K) = map(int, input().split())
	s = '%.8f' % (1.0 / solve(N, K))
	print(s)


def get_perfect_pow(n):
	nearest_power = 1
	while n > 1:
		n = n >> 1
		nearest_power = nearest_power << 1
	return nearest_power
res_cache = {}

def f(n, k, r=0):
	if (n, k, r) in res_cache:
		return res_cache[n, k, r]
	if k == 0:
		p = 1 / n
	elif n <= 2 and k >= 1:
		p = 1.0 if n == 1 or (n == 2 and r > 0) else 0.5
	elif r == 0:
		if n & 1 == 1:
			part_1 = n // 2
			part_2 = n - part_1
			even = part_1
			odd = part_2
			if part_1 & 1 == 1:
				odd = part_1
				even = part_2
			else:
				even = part_1
				odd = part_2
			p = f(odd, k - 1, even) if odd > even else f(even, k - 1, odd)
		else:
			part_1 = n // 2
			part_2 = part_1
			if part_1 & 1 == 1:
				part_1 -= 1
				part_2 += 1
			p = f(part_1, k - 1, part_2) if part_1 > part_2 else f(part_2, k - 1, part_1)
	elif r > 0:
		while n > 2 and k > 0:
			part_1 = n // 2
			part_2 = n - part_1
			n = part_1 if part_1 > part_2 else part_2
			k -= 1
		p = f(n, k, r)
	res_cache[n, k, r] = p
	return p
t = int(input())
while t > 0:
	[n, k] = [int(x) for x in input().split(' ')]
	print(f(n, k))
	t -= 1


def pro(n, k):
	if not n & 1 and n // 2 & 1:
		if k == 0:
			return float(1 / n)
		n = n // 2 + 1
		k -= 1
	while n > 4 and k > 0:
		if n & 1:
			n = n // 2 + 1
		else:
			n = n // 2
		k -= 1
	if n == 1:
		return float(1)
	if n == 2:
		return float(1 / 2)
	if k == 0:
		return float(1 / n)
	if n == 3:
		if k == 0:
			return float(1 / 3)
		if k == 1:
			return float(1 / 2)
		if k >= 2:
			return float(1)
	if n == 4:
		if k == 0:
			return float(1 / 4)
		if k == 1:
			return float(1 / 2)
		if k >= 2:
			return float(1)
t = int(input())
while t:
	(n, k) = map(int, input().split())
	print(pro(n, k))
	t -= 1


a = []
b = 1
while b < 10000000000000000000000:
	a.append(b)
	b = b * 2
t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	if k == 1:
		if n == 1:
			print('1.000000')
		elif n == 2:
			print('0.500000')
		elif n == 3:
			print('0.500000')
		elif n == 4:
			print('0.500000')
		elif n >= 5:
			if n % 2 == 0:
				nn = n // 2
				if nn % 2 == 0:
					print(1 / nn)
				else:
					nn += 1
					print(1 / nn)
			else:
				nn = (n + 1) // 2
				print(1 / nn)
	elif n == 2:
		print('0.500000')
	else:
		if k >= len(a):
			k = len(a) - 1
		kk = a[k]
		if n % kk == 0:
			nn = n // kk
		else:
			nn = (n - n % kk + kk) // kk
		print(1 / nn)


from math import ceil
for _ in range(int(input())):
	(n, k) = [int(i) for i in input().split()]
	if n == 1:
		print(1)
		continue
	if n == 2:
		print(0.5)
		continue
	if k == 0:
		print(1 / n)
		continue
	if n % 4 == 0:
		n = n / 2
	elif n % 4 == 1:
		n = (n + 1) / 2
	elif n % 4 == 2:
		n = n / 2 + 1
	else:
		n = (n + 1) / 2
	k -= 1
	for i in range(k):
		n = ceil(n / 2)
		if n == 1:
			break
	print(1 / n)


for _ in range(int(input())):
	(n, k) = [int(X) for X in input().split()]
	if n == 1 or n == 2:
		print('{:.10f}'.format(1 / n))
		continue
	for x in range(k):
		if x == 0 and n % 4 == 2:
			n -= (n - 2) // 2
		else:
			n = n - n // 2
		if n == 1:
			break
	print('{:.10f}'.format(1 / n))


a = int(input())
for _ in range(a):
	(c, b) = list(map(int, input().rstrip().split()))
	if c != 2:
		for i in range(b):
			if c == 1:
				break
			k = int(c / 2)
			if c % 2 == 0:
				if k % 2 == 0 or k == 1:
					c = k
				elif i == 0:
					c = k + 1
				else:
					c = k
			else:
				c = k + 1
	print(1.0 / c)


import sys
T = int(sys.stdin.readline())
for _ in range(T):
	(N, K) = map(int, sys.stdin.readline().split())
	D = 0
	while K and N > 2:
		if N & 1:
			D += N - (N // 2 + 1)
			N = N // 2 + 1
		elif N & 2 and D < 2:
			D += 2 * (N // 4)
			N -= 2 * (N // 4)
		else:
			D += N // 2
			N //= 2
		K -= 1
	if K and D:
		N = 1
	print(1 / N)


from math import *
from random import *
t = int(input())
for l in range(t):
	(n, k) = map(int, input().split())
	if n < 3:
		print(1 / float(n))
		continue
	if k != 0 and (n % 2 != 0 or (n % 2 == 0 and n / 2 % 2)):
		n = n // 2 + 1
		k -= 1
	elif k != 0:
		n = n // 2
		k -= 1
	for i in range(k):
		if n == 2:
			n = 1
		if n % 2 != 0:
			n = n // 2 + 1
		else:
			n = n // 2
		if n == 1:
			break
	print(1 / float(n))


def log2(n):
	x = 1
	k = 0
	while x < n:
		x *= 2
		k += 1
	return k

def prob_coins(c, w):

	def aux(coins, weights, first):
		if weights == 0:
			return 1 / coins
		elif first:
			return aux(2 * (coins // 4) + min(2, coins % 4), weights - 1, False)
		else:
			return aux((coins + 1) // 2, weights - 1, False)
	if c <= 2:
		return 1 / c
	else:
		return aux(c, w, True)
for _ in range(int(input())):
	(coins, weights) = map(float, input().split())
	if weights >= log2(coins):
		if coins == 2:
			print('{0:.8f}'.format(0.5))
		else:
			print('{0:.8f}'.format(1))
	else:
		print('{0:.8f}'.format(prob_coins(coins, weights)))


t = int(input())

def prob(n, k):
	if n == 2:
		return 0.5
	if n == 1:
		return 1
	for j in range(k):
		if n == 2:
			return 1
		if j == 0 and n % 4 == 2:
			n = n // 2 + 1
		else:
			n = (n + 1) // 2
	return 1.0 / n
for _ in range(t):
	(n, k) = [int(x) for x in input().split()]
	print(prob(n, k))


def remain(n, k, extra):
	if n <= 1:
		return 1
	if k <= 0:
		return n
	if n % 2:
		return remain((n + 1) / 2, k - 1, True)
	if n / 2 % 2 == 0 or extra:
		return remain(n / 2, k - 1, True)
	return remain(n / 2 + 1, k - 1, True)
for _ in range(int(input())):
	(n, k) = (int(x) for x in input().split())
	rem = 2 if n == 2 else remain(n, k, False)
	print('{:.7f}'.format(1 / rem))


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	if k == 0:
		print('%.6f' % (1.0 / n))
		continue
	if n == 2:
		print('%.6f' % 0.5)
		continue
	if n % 4 == 2:
		n = n // 2 + 1
	else:
		n = (n + 1) // 2
	k -= 1
	for i in range(k):
		n = (n + 1) // 2
		if n < 2:
			break
	if n < 2:
		print('%.6f' % 1.0)
	else:
		print('%.6f' % (1.0 / n))


def readInt():
	return int(input())

def readInts():
	return [int(x) for x in input().split()]

def cases():
	numCases = readInt()
	for _ in range(numCases):
		(n, k) = readInts()
		yield (n, k)

def solve(n, k):
	if k == 0 or n <= 2:
		return 1 / n
	rem = n % 4
	if rem == 0:
		n = n // 2
	elif rem == 1:
		n = (n + 1) // 2
	elif rem == 2:
		n = (n + 2) // 2
	else:
		n = (n + 1) // 2
	k -= 1
	for _ in range(k):
		n = (n + 1) // 2
		if n == 1:
			break
	return 1 / n
for data in cases():
	print(solve(*data))