codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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]$.