1854A1.md (2924B)
1 Source: https://codeforces.com/problemset/problem/1854/A1 2 3 A1. Dual (Easy Version) 4 5 time limit per test 6 7 1 second 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 [Popskyy & tiasu - Dual](https://soundcloud.com/popskyy/popskyy-tiasu-dual) 22 23 ⠀ 24 25 The only difference between the two versions of this problem is the constraint on the maximum number of operations. You can make hacks only if all versions of the problem are solved. 26 27 You are given an array $a_1, a_2,\dots, a_n$ of integers (positive, negative or $0$). You can perform multiple operations on the array (possibly $0$ operations). 28 29 In one operation, you choose $i, j$ ($1 \leq i, j \leq n$, they can be equal) and set $a_i := a_i + a_j$ (i.e., add $a_j$ to $a_i$). 30 31 Make the array non-decreasing (i.e., $a_i \leq a_{i+1}$ for $1 \leq i \leq n-1$) in at most $50$ operations. You do not need to minimize the number of operations. 32 33 Input 34 35 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 500$). The description of the test cases follows. 36 37 The first line contains a single integer $n$ ($1 \le n \le 20$) — the length of the array. 38 39 The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($-20 \le a_i \le 20$) — the array before performing the operations. 40 41 Output 42 43 For each test case, output your operations in the following format. 44 45 The first line should contain an integer $k$ ($0 \le k \le 50$) — the number of operations. 46 47 The next $k$ lines represent the $k$ operations in order. Each of these $k$ lines should contain two integers $i$ and $j$ ($1 \leq i, j \leq n$) — the corresponding operation consists in adding $a_j$ to $a_i$. 48 49 After all the operations, the array $a_1, a_2,\dots, a_n$ must be non-decreasing. 50 51 Example 52 53 Input 54 55 ``` 56 10 57 58 2 59 60 2 1 61 62 4 63 64 1 2 -10 3 65 66 5 67 68 2 1 1 1 1 69 70 8 71 72 0 0 0 0 0 0 0 0 73 74 5 75 76 1 2 -4 3 -10 77 78 10 79 80 11 12 13 14 15 -15 -16 -17 -18 -19 81 82 7 83 84 1 9 3 -4 -3 -2 -1 85 86 3 87 88 10 9 8 89 90 20 91 92 1 -14 2 -10 6 -5 10 -13 10 7 -14 19 -5 19 1 18 -16 -7 12 8 93 94 20 95 96 -15 -17 -13 8 14 -13 10 -4 11 -4 -16 -6 15 -4 -2 7 -9 5 -5 17 97 ``` 98 99 Output 100 101 ``` 102 1 103 2 1 104 3 105 4 4 106 4 4 107 3 4 108 4 109 2 1 110 3 1 111 4 1 112 5 1 113 0 114 7 115 3 4 116 3 4 117 5 4 118 5 4 119 5 4 120 5 4 121 5 4 122 15 123 6 1 124 6 1 125 6 1 126 7 2 127 7 2 128 7 2 129 8 3 130 8 3 131 8 3 132 9 4 133 9 4 134 9 4 135 10 5 136 10 5 137 10 5 138 8 139 3 4 140 3 4 141 2 4 142 2 4 143 2 4 144 2 4 145 1 4 146 1 4 147 3 148 2 1 149 3 1 150 3 1 151 31 152 14 1 153 18 7 154 13 11 155 15 11 156 6 4 157 5 17 158 19 6 159 19 12 160 10 5 161 11 12 162 1 17 163 15 19 164 16 10 165 14 2 166 16 11 167 20 7 168 7 6 169 9 5 170 3 6 171 6 14 172 17 18 173 18 14 174 12 3 175 17 16 176 8 18 177 13 16 178 9 8 179 14 8 180 16 2 181 11 8 182 12 7 183 31 184 5 12 185 19 13 186 9 1 187 5 17 188 18 19 189 6 16 190 15 8 191 6 9 192 15 14 193 7 10 194 19 7 195 17 20 196 14 4 197 15 20 198 4 3 199 1 8 200 16 12 201 16 15 202 5 6 203 12 10 204 11 15 205 20 3 206 20 19 207 13 14 208 11 14 209 18 10 210 7 3 211 12 17 212 4 7 213 13 2 214 11 13 215 ``` 216 217 Note 218 219 In the first test case, by adding $a_1 = 2$ to $a_2$, we get the array $[2, 3]$ which is non-decreasing. 220 221 In the second test case, the array changes as: 222 223 * $[1, 2, -10, 3]$ 224 * $[1, 2, -10, 6]$ 225 * $[1, 2, -10, 12]$ 226 * $[1, 2, 2, 12]$ 227 228 In the third test case, the final array is $[2, 3, 3, 3, 3]$.