Least Product
Contest: Codeforces Round 917 (Div. 2)
Difficulty rating: 800
Tags: constructive algorithms, math

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 format:
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 format:
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$$$.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

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.

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

Example output:
1
1 0
0
0
1
3 0

Editorial:
Hint $$$1$$$: What is the minimum product that we can get, when one of the given numbers is equal to $$$0$$$.
Hint $$$2$$$: How is the absolute value of the integer changed, when we apply the given operation on that integer?
Hint $$$3$$$: We can always make the product as small as possible with at most $$$1$$$ operation.
Editorial:
First, let's find the minimum product we can get. If one of the numbers is or becomes $$$0$$$, then the product will be $$$0$$$. Otherwise, all the numbers don't change their sign during the operation. So the initial product won't change its sign as well. Also, we can note that the absolute value will not increase after an operation. That means if the initial product is negative, we cannot decrease it. In this case the necessary number of operations will be $$$0$$$.
If the initial product is positive, then we know the product won't become negative, therefore we will make it zero with $$$1$$$ operation, which will be the answer and the operation will be changing any number to $$$0$$$. If the initial product is zero, then we don't need to change anything, so the number of operations needed is $$$0$$$.