← 返回题目列表

Codeforces · 1286/F

F. 哈利·波特

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

为了击败伏地魔,哈利需要首先摧毁所有魂器。最后一个魂器是一个由 $$$n$$$ 整数组成的数组 $$$a$$$,它也需要被销毁。如果数组的所有元素都为零,则认为该数组被破坏。为了破坏阵列,哈利可以执行两种类型的操作:

1. 选择一个索引 $$$i$$$ ($$$1 \le i \le n$$$),一个整数 $$$x$$$,并从 $$$a_i$$$ 中减去 $$$x$$$。
2. 选择两个索引 $$$i$$$ 和 $$$j$$$ ($$$1 \le i, j \le n; i \ne j$$$),一个整数 $$$x$$$,并从 $$$a_i$$$ 中减去 $$$x$$$,并从 $$$a_j$$$ 中减去 $$$x + 1$$$。

请注意,$$$x$$$ 不必为正数。

哈利很着急,请帮他找出摧毁阵列并消灭伏地魔所需的最少操作次数。

输入

第一行包含一个整数 $$$n$$$ — 数组 $$$a$$$ 的大小 ($$$1 \le n \le 20$$$)。

以下行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ — 数组元素 ($$$-10^{15} \le a_i \le 10^{15}$$$)。

输出

输出一个整数——销毁数组 $$$a$$$ 所需的最少操作数。

示例

输入 #1

3
1 10 100

输出 #1

3

输入 #2

3
5 3 -2

输出 #2

2

输入 #3

1
0

输出 #3

0

注意

在第一个示例中,可以仅应用第一种操作三次。

在第二个例子中,可以应用第二种操作两次:首先,选择 $$$i = 2, j = 1, x = 4$$$,它将数组转换为 $$$(0, -1, -2)$$$,然后选择 $$$i = 3, j = 2, x = -2$$$ 来销毁数组。

在第三个示例中,无需执行任何操作,因为数组已被销毁。