codeforces-scrape

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

2034D.md (2642B)


      1 Source: https://codeforces.com/problemset/problem/2034/D
      2 
      3 D. Darius' Wisdom
      4 
      5 time limit per test
      6 
      7 2 seconds
      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 [Darius the Great](https://en.wikipedia.org/wiki/Darius_the_Great) is constructing $n$ stone columns, each consisting of a base and between $0$, $1$, or $2$ inscription pieces stacked on top.
     22 
     23 In each move, Darius can choose two columns $u$ and $v$ such that the difference in the number of inscriptions between these columns is exactly $1$, and transfer one inscription from the column with more inscriptions to the other one. It is guaranteed that at least one column contains exactly $1$ inscription.
     24 
     25  ![](https://espresso.codeforces.com/d4cdf6815b1220ffe2be57e8bcb7d42bfa773cfc.webp) 
     26 
     27 Since beauty is the main pillar of historical buildings, Darius wants the columns to have ascending heights. To avoid excessive workers' efforts, he asks you to plan a sequence of at most $n$ moves to arrange the columns in non-decreasing order based on the number of inscriptions. Minimizing the number of moves is not required.
     28 
     29 Input
     30 
     31 The first line contains an integer $t$ — the number of test cases. ($1 \leq t \leq 3000$)
     32 
     33 The first line of each test case contains an integer $n$ — the number of stone columns. ($1 \leq n \leq 2 \cdot 10^5$)
     34 
     35 The second line contains $n$ integers $a_1, a_2, \ldots, a_n$, where $a_i \in \{0,1,2\}$ represents the initial number of inscriptions in the $i$-th column. It is guaranteed that at least one column has exactly $1$ inscription.
     36 
     37 It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.
     38 
     39 Output
     40 
     41 For each test case, output an integer $k$ — the number of moves used to sort the columns. ($0 \leq k \leq n$)
     42 
     43 Then, output $k$ lines, each containing two integers $u_i$ and $v_i$ ($1 \leq u_i, v_i \leq n$), representing the indices of the columns involved in the $i$-th move. During each move, it must hold that $|a_{u_i} - a_{v_i}| = 1$, and one inscription is transferred from the column with more inscriptions to the other.
     44 
     45 It can be proven that a valid solution always exists under the given constraints.
     46 
     47 Example
     48 
     49 Input
     50 
     51 ```
     52 3
     53 
     54 4
     55 
     56 0 2 0 1
     57 
     58 3
     59 
     60 1 2 0
     61 
     62 6
     63 
     64 0 1 1 2 2 2
     65 ```
     66 
     67 Output
     68 
     69 ```
     70 2
     71 2 4
     72 2 3
     73 2
     74 3 1
     75 2 3
     76 0
     77 ```
     78 
     79 Note
     80 
     81 Columns state in the first test case:
     82 
     83 * Initial: $0, 2, 0, 1$
     84 * After the first move: $0, 1, 0, 2$
     85 * After the second move: $0, 0, 1, 2$
     86 
     87 Columns state in the second test case:
     88 
     89 * Initial: $1, 2, 0$
     90 * After the first move: $0, 2, 1$
     91 * After the second move: $0, 1, 2$
     92 
     93 In the third test case, the column heights are already sorted in ascending order.