← 返回题目列表

Codeforces · 1348/A

A. 凤凰与平衡

中文机器翻译题面 查看原题

Phoenix 有 $$$n$$$ 硬币,重量为 $$$2^1、2^2、\dots、2^n$$$。他知道 $$$n$$$ 是偶数。

他想将硬币分成两堆,使得每堆正好有 $$$\frac{n}{2}$$$ 硬币,并且两堆之间的重量差异最小化。形式上,让 $$$a$$$ 表示第一堆中的权重之和,$$$b$$$ 表示第二堆中的权重之和。帮助 Phoenix 最小化 $$$|a-b|$$$,即 $$$a-b$$$ 的绝对值。

输入

输入由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 100$$$) — 测试用例的数量。

每个测试用例的第一行包含一个整数 $$$n$$$($$$2 \le n \le 30$$$;$$$n$$$ 为偶数)——Phoenix 拥有的硬币数量。

输出

对于每个测试用例,输出一个整数——两堆之间重量的最小可能差异。

示例

输入 #1

2
2
4

输出 #1

2
6

注意

在第一个测试用例中,Phoenix 有两个重量为 $$$2$$$ 和 $$$4$$$ 的硬币。不管他怎么分硬币,差额都是$$$4-2=2$$$。

在第二个测试用例中,Phoenix 有四枚重量为 $$$2$$$、$$$4$$$、$$$8$$$ 和 $$$16$$$ 的硬币。 Phoenix 的最佳选择是将重量为 $$$2$$$ 和 $$$16$$$ 的硬币放在一堆,将重量为 $$$4$$$ 和 $$$8$$$ 的硬币放在另一堆。差别是$$$(2+16)-(4+8)=6$$$。