A13399. Phoenix and Balance
编程题
普及/提高-
知识点
题目描述
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$ .
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$ .
输入格式
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.
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.
输出格式
For each test case, output one integer — the minimum possible difference of weights between the two piles.
输入输出样例
输入 #1
2 2 4
输出 #1
2 6
说明/提示
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$ .
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$ .