Codeforces Round 612 (Div. 1) |
---|
Finished |
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 if all its elements are zeroes. To destroy the array, Harry can perform two types of operations:
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$$$.
3 1 10 100
3
3 5 3 -2
2
1 0
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.
Name |
---|