codeforces-scrape

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

1762B.md (2237B)


      1 Source: https://codeforces.com/problemset/problem/1762/B
      2 
      3 B. Make Array Good
      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 An array $b$ of $m$ positive integers is good if for all pairs $i$ and $j$ ($1 \leq i,j \leq m$), $\max(b_i,b_j)$ is divisible by $\min(b_i,b_j)$.
     22 
     23 You are given an array $a$ of $n$ positive integers. You can perform the following operation:
     24 
     25 * Select an index $i$ ($1 \leq i \leq n$) and an integer $x$ ($0 \leq x \leq a_i$) and add $x$ to $a_i$, in other words, $a_i := a_i+x$.
     26 * After this operation, $a_i \leq 10^{18}$ should be satisfied.
     27 
     28 You have to construct a sequence of at most $n$ operations that will make $a$ good. It can be proven that under the constraints of the problem, such a sequence of operations always exists.
     29 
     30 Input
     31 
     32 Each test contains multiple test cases. The first line contains a single integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases. The description of the test cases follows.
     33 
     34 The first line of each test case contains a single integer $n$ ($1 \leq n \leq 10^5$) — the length of the array $a$.
     35 
     36 The second line of each test case contains $n$ space-separated integers $a_1,a_2,\ldots,a_n$ ($1 \leq a_i \leq 10^9$) — representing the array $a$.
     37 
     38 It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.
     39 
     40 Output
     41 
     42 For each test, output a single integer $p$ ($0 \leq p \leq n$) — denoting the number of operations in your solution.
     43 
     44 In each of the following $p$ lines, output two space-separated integers — $i$ and $x$.
     45 
     46 You do not need to minimize the number of operations. It can be proven that a solution always exists.
     47 
     48 Example
     49 
     50 Input
     51 
     52 ```
     53 4
     54 
     55 4
     56 
     57 2 3 5 5
     58 
     59 2
     60 
     61 4 8
     62 
     63 5
     64 
     65 3 4 343 5 6
     66 
     67 3
     68 
     69 31 5 17
     70 ```
     71 
     72 Output
     73 
     74 ```
     75 4
     76 1 2
     77 1 1
     78 2 2
     79 3 0
     80 0
     81 5
     82 1 3
     83 1 4
     84 2 1
     85 5 4
     86 3 7
     87 3
     88 1 29
     89 2 5
     90 3 3
     91 ```
     92 
     93 Note
     94 
     95 In the first test case, array $a$ becomes $[5,5,5,5]$ after the operations. It is easy to see that $[5,5,5,5]$ is good.
     96 
     97 In the second test case, array $a$ is already good.
     98 
     99 In the third test case, after performing the operations, array $a$ becomes $[10,5,350,5,10]$, which is good.
    100 
    101 In the fourth test case, after performing the operations, array $a$ becomes $[60,10,20]$, which is good.