Дан массив $$$a$$$ из $$$n$$$ элементов, каждый элемент равен $$$-1$$$, $$$0$$$ или $$$1$$$. За одну операцию вы можете выбрать индекс $$$i$$$ и увеличить $$$a_i$$$ на $$$1$$$ (то есть присвоить $$$a_i := a_i + 1$$$). Операции можно выполнять любое количество раз, выбирая любые индексы.
Требуется за наименьшее количество операций сделать произведение всех элементов массива строго положительным, то есть $$$a_1 \cdot a_2 \cdot a_3 \cdot \ldots \cdot a_n \gt 0$$$. Найдите минимальное количество операций.
Гарантируется, что это всегда возможно.
Каждый тест состоит из нескольких наборов входных данных.
В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 8$$$) — длина массива $$$a$$$.
Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$, где $$$-1 \le a_i \le 1$$$. — элементы массива $$$a$$$.
Для каждого набора выведите одно целое число — минимальное количество операций, необходимое, чтобы произведение элементов массива стало строго положительным.
33-1 0 14-1 -1 0 15-1 -1 -1 0 0
314
В первом наборе входных данных: из $$$[-1, 0, 1]$$$ можно получить $$$[1, 1, 1]$$$ за $$$3$$$ операции.
Во втором наборе входных данных: достаточно сделать $$$0 \to 1$$$ (1 операция). В итоговом массиве $$$a=[-1,-1,1,1]$$$ произведение всех элементов — $$$1$$$.
В третьем наборе входных данных: два нуля превращаем в единицы (2 операции), и один $$$-1$$$ в $$$1$$$ (ещё 2 операции), итого — $$$4$$$.
| Codeforces Round 1054 (Div. 3) |
|---|
| Закончено |
