1799B.md (2541B)
1 Source: https://codeforces.com/problemset/problem/1799/B 2 3 B. Equalize by Divide 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 You are given an array $a_1, a_2, \ldots, a_n$ of positive integers. 22 23 You can make this operation multiple (possibly zero) times: 24 25 * Choose two indices $i$, $j$ ($1 \leq i, j \leq n$, $i \neq j$). 26 * Assign $a_i := \lceil \frac{a_i}{a_j} \rceil$. Here $\lceil x \rceil$ denotes $x$ rounded up to the smallest integer $\geq x$. 27 28 Is it possible to make all array elements equal by some sequence of operations (possibly empty)? If yes, print any way to do it in at most $30n$ operations. 29 30 It can be proven, that under the problem constraints, if some way exists to make all elements equal, there exists a way with at most $30n$ operations. 31 32 Input 33 34 The first line contains a single integer $t$ ($1 \leq t \leq 1000$) — the number of test cases. Descriptions of test cases follow. 35 36 The first line of each test case description contains a single integer $n$ ($1 \leq n \leq 100$). 37 38 The second line of each test case description contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq 10^9$). 39 40 It is guaranteed, that the sum of $n$ for all test cases does not exceed $1000$. 41 42 Output 43 44 For each test case print a single integer $q$ ($-1 \leq q \leq 30n$). If $q=-1$, there is no solution, otherwise $q$ is equal to the number of operations. 45 46 If $q \geq 0$, on the next $q$ lines print two integers $i$, $j$ ($1 \leq i, j \leq n$, $i \neq j$) — descriptions of operations. 47 48 If there are multiple solutions, you can print any. 49 50 Example 51 52 Input 53 54 ``` 55 10 56 57 1 58 59 100 60 61 3 62 63 1 1 1 64 65 2 66 67 2 1 68 69 2 70 71 5 5 72 73 3 74 75 4 3 2 76 77 4 78 79 3 3 4 4 80 81 2 82 83 2 100 84 85 5 86 87 5 3 6 7 8 88 89 6 90 91 3 3 80 3 8 3 92 93 4 94 95 19 40 19 55 96 ``` 97 98 Output 99 100 ``` 101 0 102 0 103 -1 104 0 105 2 106 1 3 107 2 1 108 4 109 3 1 110 4 2 111 1 3 112 2 4 113 6 114 2 1 115 2 1 116 2 1 117 2 1 118 2 1 119 2 1 120 8 121 5 2 122 4 2 123 3 2 124 1 3 125 1 3 126 2 1 127 4 1 128 5 1 129 4 130 5 1 131 3 1 132 3 1 133 3 1 134 9 135 4 2 136 2 1 137 1 2 138 1 2 139 3 2 140 3 2 141 1 4 142 2 4 143 3 4 144 ``` 145 146 Note 147 148 In the first and second, fourth test cases all numbers are equal, so it is possible to do nothing. 149 150 In the third test case, it is impossible to make all numbers equal. 151 152 In the fifth test case: $[\color{red}{4}, 3, \color{blue}{2}] \to [\color{blue}{2}, \color{red}{3}, 2] \to [2, 2, 2]$. 153 154 In the sixth test case: $[\color{blue}{3}, 3, \color{red}{4}, 4] \to [3, \color{blue}{3}, 2, \color{red}{4}] \to [\color{red}{3}, 3, \color{blue}{2}, 2] \to [2, \color{red}{3}, 2, \color{blue}{2}] \to [2, 2, 2, 2]$. 155 156 Here the red numbers are $i$ indices (that will be assigned), blue numbers are $j$ indices.