← 返回题目列表

Codeforces · 2149/A

A. 保持积极态度

中文机器翻译题面 查看原题

给定一个由 $$$n$$$ 元素组成的数组 $$$a$$$,其中每个元素等于 $$$-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$$$ 的元素。

输出

对于每个测试用例,输出一个整数 - 使数组中元素的乘积严格为正所需的最少操作数。

示例

输入
复制

3
3
-1 0 1
4
-1 -1 0 1
5
-1 -1 -1 0 0

输出
复制

3
1
4

注意

在第一个测试用例中:从$$$[-1, 0, 1]$$$,可以通过$$$3$$$运算得到$$$[1, 1, 1]$$$。

在第二个测试用例中:执行 $$$0 \to 1$$$ (1 次操作)就足够了。在生成的数组 $$$a=[-1,-1,1,1]$$$ 中,所有元素的乘积为 $$$1$$$。

在第三个测试用例中:将两个 0 转换为 1(2 次操作),将一个 $$$-1$$$ 转换为 $$$1$$$(另外 2 次操作),总共 $$$4$$$。