310983: CF1917A. Least Product

A. Least Producttime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

You are given an array of integers $a_1, a_2, \dots, a_n$. You can perform the following operation any number of times (possibly zero):

• Choose any element $a_i$ from the array and change its value to any integer between $0$ and $a_i$ (inclusive). More formally, if $a_i < 0$, replace $a_i$ with any integer in $[a_i, 0]$, otherwise replace $a_i$ with any integer in $[0, a_i]$.

Let $r$ be the minimum possible product of all the $a_i$ after performing the operation any number of times.

Find the minimum number of operations required to make the product equal to $r$. Also, print one such shortest sequence of operations. If there are multiple answers, you can print any of them.

Input

Each test consists of multiple test cases. The first line contains a single integer $t$ ($1 \leq t \leq 500$) - the number of test cases. This is followed by their description.

The first line of each test case contains the a single integer $n$ ($1 \leq n \leq 100$) — the length of the array.

The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($-10^9 \leq a_i \leq 10^9$).

Output

For each test case:

• The first line must contain the minimum number of operations $k$ ($0 \leq k \leq n$).
• The $j$-th of the next $k$ lines must contain two integers $i$ and $x$, which represent the $j$-th operation. That operation consists in replacing $a_i$ with $x$.

ExampleInput

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

Output

1
1 0
0
0
1
3 0

Note

In the first test case, we can change the value of the first integer into $0$ and the product will become $0$, which is the minimum possible.

In the second test case, initially, the product of integers is equal to $2 \cdot 8 \cdot (-1) \cdot 3 = -48$ which is the minimum possible, so we should do nothing in this case.

题目大意：
题目名为“最小乘积”，给定一个整数数组 $a_1, a_2, \dots, a_n$，你可以进行任意次数（可能为零）的以下操作：
- 从数组中选择任意元素 $a_i$ 并将其值更改为介于 $0$ 和 $a_i$ 之间（包括 $0$ 和 $a_i$）的任何整数。更正式地说，如果 $a_i < 0$，用区间 $[a_i, 0]$ 内的任何整数替换 $a_i$，否则用区间 $[0, a_i]$ 内的任何整数替换 $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$ 次操作。该操作包括用 $x$ 替换 $a_i$。

示例输入输出已给出，不再重复。题目大意： 题目名为“最小乘积”，给定一个整数数组 $a_1, a_2, \dots, a_n$，你可以进行任意次数（可能为零）的以下操作： - 从数组中选择任意元素 $a_i$ 并将其值更改为介于 $0$ 和 $a_i$ 之间（包括 $0$ 和 $a_i$）的任何整数。更正式地说，如果 $a_i < 0$，用区间 $[a_i, 0]$ 内的任何整数替换 $a_i$，否则用区间 $[0, a_i]$ 内的任何整数替换 $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$ 次操作。该操作包括用 $x$ 替换 $a_i$。 示例输入输出已给出，不再重复。