← 返回题目列表

Codeforces · 1032/E

E. 无法承受的重量之轻

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

您有一组 $$$n$$$ 权重。您知道它们的质量为 $$$a_1$$$、$$$a_2$$$、...、$$$a_n$$$ 克,但您不知道其中哪个质量是多少。你无法区分重量。

但是,您的朋友确实知道每个重量的质量。您可以要求您的朋友为您提供精确的 $$$k$$$ 权重和总质量 $$$m$$$(参数 $$$k$$$ 和 $$$m$$$ 均由您选择),并且您的朋友将指出任何有效的权重子集(如果可能)。

您只能进行一次此查询。找出在此查询后可以显示的最大可能权重数。

输入

第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 100$$$) — 权重的数量。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 100$$$) — 权重的质量。

输出

打印进行一次查询后可以了解质量的最大权重数。

示例

输入 #1

4
1 4 2 2

输出 #1

2

输入 #2

6
1 2 4 4 4 9

输出 #2

2

注意

在第一个示例中,我们可以要求总质量等于 $$$4$$$ 的两个权重的子集,唯一的选择是获取 $$$\{2, 2\}$$$。

获得相同结果的另一种方法是要求总质量为 $$$5$$$ 的两个权重的子集,并得到 $$$\{1, 4\}$$$。很容易看出剩下的两个重量各有 $$$2$$$ 克的质量。

在第二个示例中,我们可以要求总质量为 $$$8$$$ 的两个权重的子集,唯一的答案是 $$$\{4, 4\}$$$。我们可以证明不可能在一个查询中学习三个权重的质量,但我们不会在这里给出证明。