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

We have a rectangular piece of cardboard with width $1$ (its height is not important). We are going to fold it in the following way:
pick up the right side of the piece of cardboard and move it to the left until it touches the left side
this way, a smaller piece of cardboard with width $1/2$ is created; if we unfolded it, we could see a vertical ridge formed in the middle
pick up the left side of this new piece of cardboard and move it to the right until it touches the (new) right side
pick up the right side of the resulting piece of cardboard and move it to the left until it touches the left side, etc.

Whenever the cardboard is folded, exactly one of its new sides is a newly formed ridge (there may be more, internal ridges formed, but we do not consider these). Let's denote such a ridge created in the $k$-th folding by $R_{k}$.

In total, we fold the piece of cardboard $N$ times. Afterwards, we unfold it and look at the formed ridges. Let's denote the distance of ridge $R_{N}$ (i.e. the last formed outer ridge) from the left side of the original piece of cardboard by $D_{N}$. For example, $D_{1} = 1/2$ and $D_{2} = 1/4$.

It is possible to express $D_{N}$ as an irreducible fraction $x/y$. Find this fraction.

Assume that it is possible to fold the piece of cardboard as many times as we want.

------  Input ------
The first and only line of the input contains a single integer $T$ denoting the number of test cases. For each test case, a space and an integer $N$ follows.

------  Output ------
Print a single line containing $2T$ space-separated integers. For the $i$-th test case ($1 ≤ i ≤ T$), the $2i-1$-th and $2i$-th integer should denote $x$ and $y$ — the position of the last ridge as an irreducible fraction.

------  Constraints ------
$1 ≤ T ≤ 5$
$1 ≤ N ≤ 25$

Subtask #1 (10 points):
$1 ≤ T ≤ 5$
$1 ≤ N ≤ 5$

Subtask #2 (90 points): original constraints

----- Sample Input 1 ------ 
2 1 2
----- Sample Output 1 ------ 
1 2 1 4
----- explanation 1 ------ 
Example case 1: We only fold once, so $x=1$ and $y=2$.

Example case 2: We fold the piece of cardboard twice. The last edge is at $1/4$, so $x=1$ and $y=4$.

Difficulty: MEDIUM
Tags: Mathematics

Number theory

Implementation

Starter code:

Solutions:
inp = input().split()
for i in range(int(inp[0])):
	n = int(inp[i + 1])
	num = 1
	for i in range(2, n + 1):
		if i % 2 == 0:
			num = 2 * num - 1
		else:
			num = 2 * num + 1
	print('{} {}'.format(num, 2 ** n), end=' ')


import math
lst = list(map(int, input().split()))
length = len(lst)
anslst = []
for i in range(1, length):
	v = lst[i]
	if v % 2 == 0:
		numerator = 2 ** v - 1
	else:
		numerator = 2 ** v + 1
	denominator = 3 * 2 ** v
	gcd = math.gcd(numerator, denominator)
	anslst.append(numerator // gcd)
	anslst.append(denominator // gcd)
print(*anslst)


lst0 = list(map(int, input().split()))
lst0.pop(0)
m = max(lst0)
lst1 = [0, 1]
for i in range(m - 1):
	lst1.append(lst1[-1] + lst1[-2] * 2)
for j in lst0:
	print(lst1[j], 2 ** j, end=' ')


N = list(map(int, input().split()))
pp = []
for i in N[1:]:
	n = 1
	k = 2
	for i in range(k, i + 1):
		u = i % 2
		if u == 0:
			n = k * n - 1
		else:
			n = k * n + 1
	pp.append(n)
	pp.append(2 ** i)
print(*pp)


l = list(map(int, input().split()))
temp = []
for i in l[1:]:
	num = 1
	cnt = 2
	for i in range(cnt, i + 1):
		if i % 2 == 0:
			num = cnt * num - 1
		else:
			num = cnt * num + 1
	temp.append(num)
	temp.append(2 ** i)
print(*temp)


x = input().split()
t = int(x.pop(0))
for i in range(t):
	n = int(x[i])
	p = 2 ** n
	if n % 2:
		print((p + 1) // 3, end=' ')
	else:
		print((p - 1) // 3, end=' ')
	print(p, end=' ')
print()


arrf = []
arrf.append([1, 2])
arrf.append([1, 4])
for i in range(2, 26):
	value = arrf[i - 2][0] * 2 + arrf[i - 1][0]
	arrf.append([value, pow(2, i + 1)])
arr = list(map(int, input().split()))
for j in range(1, arr[0] + 1):
	print(arrf[arr[j] - 1][0], arrf[arr[j] - 1][1], end=' ')
print()


l = list(map(int, input().split()))
c = []
for i in l[1:]:
	a = (2 ** i - (-1) ** i) // 3
	b = 2 ** i
	c.append(a)
	c.append(b)
print(*c)


t = list(map(int, input().split()))
ans = []
for i in t[1:]:
	a = i
	n = (2 ** a - (-1) ** a) // 3
	d = 2 ** a
	ans.append(n)
	ans.append(d)
print(*ans)


c = list(map(int, input().split()))
ans = []
for i in c[1:]:
	n = i
	num = (2 ** n - (-1) ** n) // 3
	den = 2 ** n
	ans.append(num)
	ans.append(den)
print(*ans)


t = list(map(int, input().split()))
t.pop(0)
m = max(t)
l = [0, 1]
for i in range(m - 1):
	l.append(l[-1] + l[-2] * 2)
for j in t:
	print(l[j], 2 ** j, end=' ')


from fractions import Fraction
list1 = [int(x) for x in input().split()]
del list1[0]
for n in list1:
	left_ridge = 0.0
	right_ridge = 1.0
	ans = 0.0
	for i in range(n):
		temp_ridge = (left_ridge + right_ridge) / 2
		if i % 2 == 0:
			ans = right_ridge = temp_ridge
		else:
			ans = left_ridge = temp_ridge
	ans = Fraction(ans)
	print(ans.numerator, ans.denominator, end=' ')
print()


from fractions import Fraction
N = list(map(int, input().split()))
del N[0]
for n in N:
	left_ridge = 0.0
	right_ridge = 1.0
	ans = 0.0
	for i in range(n):
		temp_ridge = (left_ridge + right_ridge) / 2
		if i % 2 == 0:
			ans = right_ridge = temp_ridge
		else:
			ans = left_ridge = temp_ridge
	ans = Fraction(ans)
	print(ans.numerator, ans.denominator, end=' ')
print()


import decimal
decimal_value = -0.375
decimal_object = decimal.Decimal(decimal_value)
(numerator, denominator) = decimal_object.as_integer_ratio()
l = []
A = list(map(int, input().split()))
N = A.pop(0)
for i in range(N):
	sum = 0
	for j in range(A[i]):
		if j % 2 != 0:
			sum -= 1 / 2 ** (j + 1)
		else:
			sum += 1 / 2 ** (j + 1)
	decimal_value = sum
	decimal_object = decimal.Decimal(decimal_value)
	(numerator, denominator) = decimal_object.as_integer_ratio()
	l.append(numerator)
	l.append(denominator)
print(*l)


from sys import stdin
seq = lambda : list(map(int, stdin.readline().strip().split()))
data = seq()
for i in range(data[0]):
	d = pow(2, data[i + 1])
	v = [0] * 25
	v[0] = d // 2
	v[1] = d // 4
	for j in range(2, data[i + 1]):
		v[j] = (v[j - 1] + v[j - 2]) // 2
	print(v[data[i + 1] - 1], end=' ')
	print(d, end=' ')


L = list(map(int, input().split()))
curr = 0
A = []
for i in range(25 + 1):
	if i % 2 == 0:
		curr = curr * 2 + 1
	else:
		curr = curr * 2 - 1
	A.append(curr)
for i in range(1, len(L)):
	question = L[i]
	ans1 = A[question - 1]
	ans2 = 2 ** question
	print(ans1, ans2, end=' ')


from fractions import Fraction
maxval = 25
value = [0, (1, 2), (1, 4)]
for i in range(3, maxval + 1):
	value.append((1 * value[i - 2][1] + value[i - 2][0], value[i - 2][1] * 4))
arr = list(map(int, input().split(' ')))
for i in range(1, len(arr)):
	print(value[arr[i]][0], value[arr[i]][1], end=' ')


a = list(map(int, input().split()))
t = a[0]
n = a[1:]
for i in n:
	print((2 ** i - -1 ** i) // 3, end=' ')
	print(2 ** i, end=' ')


a = list(map(int, input().split()))
s = a[0]
d = a[1:]
for i in d:
	print((2 ** i - -1 ** i) // 3, end=' ')
	print(2 ** i, end=' ')


T = list(map(int, input().split()))
for i in range(1, T[0] + 1):
	(a, b) = ([1, 2], [1, 4])
	if T[i] == 1:
		print(*a, end=' ')
	elif T[i] == 2:
		print(*b, end=' ')
	else:
		for _ in range(2, T[i]):
			c = [b[0] + 2 * a[0], 2 * b[1]]
			(a, b) = (b, c)
		print(*b, end=' ')


dad = list(map(int, input().split()))
sai = dad[0]
dad = dad[1:]
for i in dad:
	print(f'{(2 ** i - -1 ** i) // 3}', end=' ')
	print(f'{2 ** i}', end=' ')


arr = list(map(int, input().split()))
t = arr[0]
arr = arr[1:]
for i in arr:
	print(f'{(2 ** i - -1 ** i) // 3}', end=' ')
	print(f'{2 ** i}', end=' ')


l = list(map(int, input().split()))
for i in range(l[0]):
	n = l[i + 1]
	print((2 ** l[i + 1] - (-1) ** l[i + 1]) // 3, end=' ')
	print(2 ** n, end=' ')


l = ['1 2']
n = 1
d = 2
for i in range(2, 26):
	(n, d) = (d - n, 2 * d)
	l.append(f'{n} {d}')
a = list(map(int, input().split()))
print(' '.join((l[x - 1] for x in a[1:])))


tests = list(map(int, input().split()))
ans = []
numerator_arr = [1, 1]
for i in range(24):
	numerator_arr.append(numerator_arr[-2] * 2 + numerator_arr[-1])
for i in range(1, tests[0] + 1):
	numerator = numerator_arr[tests[i] - 1]
	denominator = 2 ** tests[i]
	ans.extend([numerator, denominator])
print(*ans)


l = list(map(int, input().split()))
t = l[0]
for i in range(1, len(l)):
	n = l[i]
	res = 0
	j = 1
	for i in range(n - 1, -1, -1):
		if j:
			res += pow(2, i)
		else:
			res -= pow(2, i)
		j ^= 1
	print(res, end=' ')
	print(pow(2, n), end=' ')


ns = list(map(int, input().split()))
ns.pop(0)
for n in ns:
	d = 2 ** n
	l = [d // 2, d // 4]
	for i in range(2, n):
		l.append(int(l[i - 1] + l[i - 2]) // 2)
	print(str(l[n - 1]) + ' ' + str(d) + ' ', end='')


a = list(map(int, input().split()))
for n in a[1:]:
	(l, r) = (0, 1)
	for i in range(n):
		if i % 2:
			l = (l + r) / 2
		else:
			r = (l + r) / 2
	x = r if n % 2 else l
	y = 1
	while int(x) != x:
		x *= 2
		y *= 2
	print(int(x), y, end=' ')


arr = list(map(int, input().split()))
T = arr.pop(0)
i = 0
s = ''
while T > 0:
	n = arr[i]
	if n == 1:
		k = 1 / 2
	elif n == 2:
		k = 1 / 4
	else:
		k = 1 / 4 + 1 / 12 * (1 - (-1 / 2) ** (n - 2))
	c = 1
	while True:
		z = 2 ** c * k
		if int(z) == z:
			break
		c += 1
	s += str(int(z)) + ' ' + str(int(2 ** c)) + ' '
	i += 1
	T -= 1
print(s.strip())


def gcd(x, y):
	if y == 0:
		return x
	else:
		return gcd(y, x % y)

def lcm(x, y):
	return int(x / gcd(x, y) * y)
inp = list(map(int, input().split()))
T = inp[0]
Narr = inp[1:T + 1]
dn = [[0, 0] for i in range(25)]
(dn[0][0], dn[0][1]) = (1, 2)
(dn[1][0], dn[1][1]) = (1, 4)
for i in range(2, 25):
	dn[i][1] = lcm(dn[i - 1][1], dn[i - 2][1])
	dn[i][0] = dn[i - 1][0] * (dn[i][1] // dn[i - 1][1]) + dn[i - 2][0] * (dn[i][1] // dn[i - 2][1])
	dn[i][1] *= 2
for N in Narr:
	print(dn[N - 1][0], dn[N - 1][1], end=' ')


t = list(map(int, input().split()))
b = t[1:]
for j in b:
	if j == 1:
		x = 1
		y = 2
	else:
		x = 1
		y = 2
		for k in range(2, j + 1):
			if k % 2 == 0:
				x = 2 * x - 1
				y = 2 * y
			else:
				x = 2 * x + 1
				y = 2 * y
	print(x, y, end=' ')


t = list(map(int, input().split()))
a1 = t[1:]
q = []
for i in range(len(a1)):
	a = a1[i]
	if a == 1 or a == 2:
		x = 1
		y = 2 ** a
	else:
		x = 1
		y = 4
		for j in range(3, a + 1):
			if j % 2 == 0:
				x = 2 * x - 1
				y = 2 * y
			else:
				x = 2 * x + 1
				y = 2 * y
	q.append(x)
	q.append(y)
print(*q)


List = list(map(int, input().split()))
l = []
for i in List[1:]:
	if i % 2 == 0:
		l.append((2 ** i - 1) // 3)
		l.append(2 ** i)
	else:
		l.append((2 ** i + 1) // 3)
		l.append(2 ** i)
for x in l:
	print(x, end=' ')


from math import gcd
l = list(map(int, input().split()))
m = max(l)
l1 = [1, 1]
for i in range(2, m):
	l1.append(l1[-2] * 2 + l1[-1])
for i in range(l[0]):
	x = l1[l[i + 1] - 1]
	y = 2 ** l[i + 1]
	g = gcd(x, y)
	print(x // g, y // g, end=' ')


T = list(map(int, input().split()))
B = T[1:]
for i in B:
	if i == 1:
		x = 1
		y = 2
	elif i == 2:
		x = 1
		y = 4
	else:
		x = 1
		y = 4
		for j in range(3, i + 1):
			if j % 2 != 0:
				x = 2 * x + 1
				y = 2 * y
			else:
				x = 2 * x - 1
				y = 2 * y
	print(x, y, end=' ')


import fileinput

def solveSingle(n, a, b, d):
	x = a + b
	if d == n:
		return f'{x} {2 ** d}'
	elif d % 2 == 1:
		return solveSingle(n, 2 * a, x, d + 1)
	else:
		return solveSingle(n, x, 2 * b, d + 1)
with fileinput.input() as f:
	line = f.readline().strip().split(' ')
	t = int(line[0])
	if t != len(line) - 1:
		raise ValueError(f'unexpected lengths {t} {len(line) - 1}')
	print(' '.join((solveSingle(int(n), 0, 1, 1) for n in line[1:])))


ans = ['append']
for i in range(1, 30 + 1):
	n = i
	l = 0
	r = 1
	next = 1
	power = 1
	for j in range(n - 1):
		next = 2 * l + r
		l = r
		r = next
		power *= 2
	power *= 2
	ans.append(str(next) + ' ' + str(power))
test = list(map(int, input().split()))
t = test[0]
for i in range(t):
	n = test[i + 1]
	print(ans[n], end=' ')


a = list(map(int, input().split()))
b = a[1:]
for i in b:
	if i == 1:
		x = 1
		y = 2
	elif i == 2:
		x = 1
		y = 4
	else:
		x = 1
		y = 4
		for j in range(3, i + 1):
			if j % 2 != 0:
				x = 2 * x + 1
				y = 2 * y
			else:
				x = 2 * x - 1
				y = 2 * y
	print(x, y, end=' ')


l = list(map(int, input().split()))
lis = []
for i in range(1, len(l)):
	if l[i] <= 2:
		lis.append(1)
		lis.append(2 ** l[i])
	else:
		a = 1
		b = 1
		m = l[i]
		while m != 2:
			a1 = a
			b1 = b
			b = 2 * a1 + b1
			a = b1
			m -= 1
		lis.append(b)
		lis.append(2 ** l[i])
print(*lis)