codeforces-scrape

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

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.