← 返回题目列表

Codeforces · 1917/A

A. 最小乘积

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

给定一个整数数组 $$$a_1, a_2, \dots, a_n$$$。您可以执行以下操作任意次数(可能为零):

- 从数组中选择任意元素 $$$a_i$$$ 并将其值更改为 $$$0$$$ 和 $$$a_i$$$(含)之间的任何整数。更正式地说,如果 $$$a_i < 0$$$,则将 $$$a_i$$$ 替换为 $$$[a_i, 0]$$$ 中的任意整数,否则将 $$$a_i$$$ 替换为 $$$[0, a_i]$$$ 中的任意整数。

令 $$$r$$$ 为执行任意次操作后所有 $$$a_i$$$ 的最小可能乘积。

求使乘积等于 $$$r$$$ 所需的最少运算次数。另外,打印一个这样的最短操作序列。如果有多个答案,您可以打印其中任何一个。

输入

每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 500$$$) - 测试用例的数量。接下来是他们的描述。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 100$$$) — 数组的长度。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$-10^9 \leq a_i \leq 10^9$$$)。

输出

对于每个测试用例:

- 第一行必须包含最少的操作数 $$$k$$$ ($$$0 \leq k \leq n$$$)。
- 接下来的 $$$k$$$ 行中的第 $$$j$$$ 行必须包含两个整数 $$$i$$$ 和 $$$x$$$,它们代表第 $$$j$$$ 操作。该操作包括将 $$$a_i$$$ 替换为 $$$x$$$。

示例

输入 #1

4
1
155
4
2 8 -1 3
4
-1 0 -2 -5
4
-15 -75 -25 -30

输出 #1

1
1 0
0
0
1
3 0

注意

在第一个测试用例中,我们可以将第一个整数的值更改为$$$0$$$,并且乘积将变为$$$0$$$,这是可能的最小值。

在第二个测试用例中,最初,整数的乘积等于 $$$2 \cdot 8 \cdot (-1) \cdot 3 = -48$$$,这是可能的最小值,因此在这种情况下我们不应该执行任何操作。