| Codeforces Round 612 (Div. 1) |
|---|
| Закончено |
Как известно, чтобы победить лорда Волан-де-Морта, Гарри необходимо сперва уничтожить все крестражи. Последний крестраж лорда Сами-Знаете-кого представляет собой массив $$$a$$$ состоящий из $$$n$$$ целых чисел, который Гарри необходимо уничтожить. Массив считается уничтоженным, если все его элементы равны 0. Чтобы его уничтожить, Гарри может производить два типа операций:
- выбрать индекс $$$i$$$ ($$$1 \le i \le n$$$), целое число $$$x$$$ и вычесть из $$$a_i$$$ число $$$x$$$.
- выбрать индексы $$$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$$$.
3 1 10 100
3
3 5 3 -2
2
1 0
0
В первом примере можно три раза применить операцию первого типа к массиву.
Во втором примере можно два раза применить операцию второго типа: сначала выбрать $$$i = 2, j = 1, x = 4$$$ и получить массив $$$(0, -1, -2)$$$, затем выбрать $$$i = 3, j = 2, x = -2$$$ чтобы уничтожить массив.
В третьем примере ничего делать не надо, так как массив уже состоит из нулей.
