CF1286F.Harry The Potter

普及/提高-

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

To defeat Lord Voldemort, Harry needs to destroy all horcruxes first. The last horcrux is an array $a$ of $n$ integers, which also needs to be destroyed. The array is considered destroyed is all its elements are zeroes. To destroy the array, Harry can perform two types of operations:

choose an index $i$ ( $1 \le i \le n$ ), an integer $x$ , and subtract $x$ from $a_i$ .
choose two indices $i$ and $j$ ( $1 \le i, j \le n; i \ne j$ ), an integer $x$ , and subtract $x$ from $a_i$ and $x + 1$ from $a_j$ .

Note that $x$ does not have to be positive.

Harry is in a hurry, please help him to find the minimum number of operations required to destroy the array and exterminate Lord Voldemort.

输入格式

The first line contains a single integer $n$ — the size of the array $a$ ( $1 \le n \le 20$ ).

The following line contains $n$ integers $a_1, a_2, \ldots, a_n$ — array elements ( $-10^{15} \le a_i \le 10^{15}$ ).

输出格式

Output a single integer — the minimum number of operations required to destroy the array $a$ .

输入输出样例

输入#1
```
3
1 10 100
```
输出#1
```
3
```
输入#2
```
3
5 3 -2
```
输出#2
```
2
```
输入#3
```
1
0
```
输出#3
```
0
```

说明/提示

In the first example one can just apply the operation of the first kind three times.

In the second example, one can apply the operation of the second kind two times: first, choose $i = 2, j = 1, x = 4$ , it transforms the array into $(0, -1, -2)$ , and then choose $i = 3, j = 2, x = -2$ to destroy the array.

In the third example, there is nothing to be done, since the array is already destroyed.

首页