← 返回题目列表

Codeforces · 949/E

E. 二进制卡

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

玩精美的“二进制卡牌”游戏永远不会太晚!

游戏中使用的正数和负数卡牌的数量是无限的。任何卡牌等级的绝对值都是 2 的幂,即对于某个整数 k ≥ 0,每张卡的等级为 2k 或 - 2k。任何有效等级的卡牌数量都是无限的。

在游戏开始时,玩家形成他的牌组,该牌组是一些多组(可能是空的)牌。允许选择任何数量的任何级别的牌,但小牌组被认为是技能指标。游戏由n轮组成。在第 i 轮中,陪审团告诉玩家一个整数 ai。之后,玩家有义务抽出他的牌组的子集,使得所选牌的等级总和等于ai(允许不抽任何牌,在这种情况下,总和被认为等于零)。如果玩家没有这样做,他就输了,游戏结束。否则,玩家将所有牌收回牌组,游戏进入下一轮。如果玩家能够在每一轮中抽出合适的牌组,则他被视为获胜者。

有人告诉你陪审团将在每一轮中告诉你哪些数字。现在您想要选择一副由最少数量的纸牌组成的牌组,以便您赢得“二元纸牌”游戏。

输入

输入的第一行包含一个整数n (1 ≤ n ≤ 100 000),即游戏的轮数。

输入的第二行包含 n 个整数 a1, a2, ..., an ( - 100 000 ≤ ai ≤ 100 000),即陪审团在每一轮中要说出的数字。

输出

在第一行中打印整数 k (0 ≤ k ≤ 100 000),即为赢得“二元卡”而必须在牌组中挑选的最小卡牌数量。

在第二行中打印 k 个整数 b1, b2, ..., bk (- 220 ≤ bi ≤ 220, |bi| 是 2 的幂),即你牌组中牌的排名。您可以按任何顺序输出排名。如果有多个最佳牌组,您可以打印其中任何一个。

保证存在满足上述所有要求的最小尺寸的牌组。

示例

输入 #1

1
9

输出 #1

2
1 8

输入 #2

5
-1 3 0 4 7

输出 #2

3
4 -1 4

输入 #3

4
2 -2 14 18

输出 #3

3
-2 2 16

注意

在第一个示例中,游戏中有唯一一轮,您可以简单地抽出两张牌。请注意,此示例测试是唯一满足第一个测试组约束的测试。

在第二个示例中,您可能在第一轮中抽出唯一的牌 - 1,在第二轮中抽出牌 4 和 - 1,在第三轮中什么都没有,在第四轮中抽出唯一的牌 4,在第五轮中抽出整副牌。