[Codeforces] 2149A - Be Positive

Given an array 𝑎 of 𝑛 elements, where each element is equal to −1, 0, or 1. In one operation, you can choose an index 𝑖 and increase 𝑎𝑖 by 1 (that is, assign 𝑎𝑖:=𝑎𝑖+1). Operations can be performed any number of times, choosing any indices.

The goal is to make the product of all elements in the array strictly positive with the minimum number of operations, that is, 𝑎1⋅𝑎2⋅𝑎3⋅…⋅𝑎𝑛>0. Find the minimum number of operations.

It is guaranteed that this is always possible.

Input

Each test consists of several test cases.

The first line contains one integer 𝑡 (1≤𝑡≤104) — the number of test cases. The description of the test cases follows.

The first line of each test case contains one integer 𝑛 (1≤𝑛≤8) — the length of the array 𝑎.

The second line contains 𝑛 integers 𝑎1,𝑎2,…,𝑎𝑛, where −1≤𝑎𝑖≤1 — the elements of the array 𝑎.

Output

For each test case, output one integer — the minimum number of operations required to make the product of the elements in the array strictly positive.

 

 

 

Note

In the first test case: from [−1,0,1], you can obtain [1,1,1] in 3 operations.

In the second test case: it is enough to perform 0→1 (1 operation). In the resulting array 𝑎=[−1,−1,1,1], the product of all elements is 1.

In the third test case: turning two zeros into ones (2 operations), and one −1 into 1 (another 2 operations), for a total of 4

 

 

 

 

🧠 핵심 논리 다시 정리

 

1. 모든 원소를 0이 아닌 상태로 만들어야 함
2. → z = a.count(0) 만큼 연산 필요.
3. 음수의 개수(m)가 짝수여야 함.
   • 짝수 → 그대로 OK
   • 홀수 → 하나를 바꿔야 함
     • 만약 0이 있다면 그 0을 -1로 바꿔서 (1회 연산) 음수 개수를 짝수로 만들 수 있음 → 추가 비용 없음.
     • 0이 없다면 -1 하나를 1로 바꿔야 함 → -1 → 0 → 1 두 번 필요 → +2.

 

 

 

 

 

 

import sys

def solve():
    it = iter(sys.stdin.read().split())
    t = int(next(it))
    out_lines = []
    for _ in range(t):
        n = int(next(it))
        a = [int(next(it)) for _ in range(n)]
        z = a.count(0)
        m = a.count(-1)
        out_lines.append(str(z + 2 * (m & 1)))
    print("\n".join(out_lines))

if __name__ == "__main__":
    solve()