5199. Extra Large Knapsack

单点时限: 1.0 sec

内存限制: 1024 MB

有一次 Compute 打比赛的时候拿到了一个超大背包,而这个背包不止大这么简单,它可以把装的物品的体积暂时改变,这就使得他可以装更多的东西。

具体地,如果背包里面装了 k 件物品,而这 k 件物品的体积分别为 w1,w2,,wk,则这 k 件物品的总体积 W 就变成了 W=i=1kwi=w1w2wk。其中 表示按位异或运算。

——第 19 届上海大学程序设计联赛春季赛 F 题

第 21 届上海大学程序设计联赛春季赛中,Compute 不出意外地又夺冠了,他又得到了一个和第 19 届上海大学程序设计联赛春季赛同样的超大背包。因此他有了两个超大背包。

在比赛结束后,他带着这两个背包来到了上海大学教育超市采购物品。他希望购买 n 件物品,同时他还希望把这些物品分成两组(每组至少一件物品),分别放到这两个背包中,且放入背包后物品的总体积 W 相等(背包中物品的总体积计算方式和第 19 届上海大学程序设计联赛春季赛的背包是相同的)。

现在,你需要帮他计算出一种可行的分组方案,或者告诉他这是不可能做到的。

输入格式

有多组测试数据,第一行包含一个整数 T (T1000) 表示测试数据的组数。对于每组测试数据:

第一行包含一个整数 n (1n10) 表示 Compute 想购买的物品的个数。

第二行包含 n 个整数 w1,w2,,wn (0wi<65536) ,中间以空格分隔,分别表示每件物品的体积。

输出格式

对于每组测试数据,如果 Compute 可以如题目描述把物品分成两组,首先输出一行”Yes” (不包含引号,不区分大小写),第二行输出一个长度为 n 的 01 串 s1s2sn,表示物品的分组方式,其中 si=0 表示第 i 个物品放入第一个背包,si=1 表示第 i 个物品放入第二个背包,如果有多种合法的答案,您可以输出任意一种;如果 Compute 无法如题目描述把物品分成两组,输出一行 “No”。

样例

Input
3
7
1 2 3 4 5 6 7
10
2 6 7 9 8 1 8 2 8 6
5
26 79 81 82 86
Output
Yes
0110011
No
Yes
00110

提示

对于第一组样例,145=2367=0

对于第三组样例,267986=8182=3

285 人解决,317 人已尝试。

316 份提交通过,共有 799 份提交。

1.9 EMB 奖励。

创建: 1 年,7 月前.

修改: 1 年,7 月前.

最后提交: 1 月前.

来源: N/A

题目标签