Phoenix and Balance (Codeforces 1348A)
Tags: Greedy, math

Phoenix has $$$n$$$ coins with weights $$$2^1, 2^2, \dots, 2^n$$$. He knows that $$$n$$$ is even.He wants to split the coins into two piles such that each pile has exactly $$$\frac{n}{2}$$$ coins and the difference of weights between the two piles is minimized. Formally, let $$$a$$$ denote the sum of weights in the first pile, and $$$b$$$ denote the sum of weights in the second pile. Help Phoenix minimize $$$|a-b|$$$, the absolute value of $$$a-b$$$.

Input: The input consists of multiple test cases. The first line contains an integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of test cases.The first line of each test case contains an integer $$$n$$$ ($$$2 \le n \le 30$$$; $$$n$$$ is even) — the number of coins that Phoenix has. 

Output: For each test case, output one integer — the minimum possible difference of weights between the two piles.

Note: In the first test case, Phoenix has two coins with weights $$$2$$$ and $$$4$$$. No matter how he divides the coins, the difference will be $$$4-2=2$$$.In the second test case, Phoenix has four coins of weight $$$2$$$, $$$4$$$, $$$8$$$, and $$$16$$$. It is optimal for Phoenix to place coins with weights $$$2$$$ and $$$16$$$ in one pile, and coins with weights $$$4$$$ and $$$8$$$ in another pile. The difference is $$$(2+16)-(4+8)=6$$$.

Sample Inputs:
2
2
4

Sample Outputs:
2
6

Solution (Python):
for j in range(int(input())):
    n = int(input())
    b = [2 ** i for i in range(1, n + 1)]
    d = b[-1]
    b.pop(-1)
    if n == 2:
        print(2)
    else:
        for f in range(n // 2 - 1):
            e = b[f]
            d += e
        g = n // 2 - 1
        h = b[g:n]
        print(abs(d - sum(h)))

Solution (Python):
def get_liste():
    answer = [0, 2]
    last = 2
    for i in range(2, 31):
        answer.append(0)
        last = last + pow(2, i)
        answer.append(last)
    return answer

def solve(tests):
    lookup = get_liste()
    for test in tests:
        print(lookup[test - 1])
tests = []
t = int(input())
for i in range(t):
    tests.append(int(input()))
solve(tests)

Solution (Python):
t = int(input())
for i in range(t):
    n = int(input())
    a = [2 ** i for i in range(1, n + 1)]
    print(sum([a[-1]] + a[:n // 2 - 1]) - sum(a[n // 2 - 1:-1]))