← 返回题目列表

Codeforces · 1221/A

A. 2048游戏

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

您正在玩游戏 2048 的变体。最初您有一个 $$$n$$$ 整数的多重集 $$$s$$$。这个多重集中的每个整数都是 2 的幂。

您可以使用此多重集执行任意次数(可能为零)的操作。

在每次操作中,您从$$$s$$$中选择两个相等的整数,将它们从$$$s$$$中删除,并将等于它们总和的数字插入到$$$s$$$中。

例如,如果 $$$s = \{1, 2, 1, 1, 4, 2, 2\}$$$ 并且您选择整数 $$$2$$$ 和 $$$2$$$,则多重集将变为 $$$\{1, 1, 1, 4, 4, 2\}$$$。

如果数字 $$$2048$$$ 属于您的多重组合,您就赢了。例如,如果 $$$s = \{1024, 512, 512, 4\}$$$,您可以通过以下方式获胜:选择 $$$512$$$ 和 $$$512$$$,您的多重集将变成 $$$\{1024, 1024, 4\}$$$。然后选择 $$$1024$$$ 和 $$$1024$$$,你的多重组合变成 $$$\{2048, 4\}$$$ 并且你赢了。

你必须确定你是否能赢得这场比赛。

您必须回答 $$$q$$$ 独立查询。

输入

第一行包含一个整数 $$$q$$$ ($$$1 \le q \le 100$$$) – 查询数量。

每个查询的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 100$$$) — 多重集中的元素数量。

每个查询的第二行包含 $$$n$$$ 整数 $$$s_1, s_2, \dots, s_n$$$ ($$$1 \le s_i \le 2^{29}$$$) — 多重集的描述。保证多重集的所有元素都是 2 的幂。

输出

对于每个查询,如果可以在多重集中获取数字 $$$2048$$$,则打印 YES,否则打印 NO。

您可以按您想要的任何大小写打印每个字母(例如,字符串 yEs、yes、Yes 和 YES 都将被识别为肯定答案)。

示例

输入 #1

6
4
1024 512 64 512
1
2048
3
64 512 2
2
4096 4
7
2048 2 2048 2048 2048 2048 2048
2
2048 4096

输出 #1

YES
YES
NO
NO
YES
YES

注意

在第一个查询中,您可以通过以下方式获胜:选择 $$$512$$$ 和 $$$512$$$,$$$s$$$ 变为 $$$\{1024, 64, 1024\}$$$。然后选择 $$$1024$$$ 和 $$$1024$$$,$$$s$$$ 变成 $$$\{2048, 64\}$$$,你就赢了。

在第二个查询 $$$s$$$ 中最初包含 $$$2048$$$。