2085B.md (3136B)
1 Source: https://codeforces.com/problemset/problem/2085/B 2 3 B. Serval and Final MEX 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$ consisting of $n\ge 4$ non-negative integers. 22 23 You need to perform the following operation on $a$ until its length becomes $1$: 24 25 * Select two indices $l$ and $r$ ($1\le {\color{red}{ l \lt r }} \le |a|$), and replace the subarray $[a_l,a_{l+1},\ldots,a_r]$ with a single integer $\operatorname{mex}([a_l,a_{l+1},\ldots,a_r])$, where $\operatorname{mex}(b)$ denotes the minimum excluded (MEX)$^{\text{∗}}$ of the integers in $b$. In other words, let $x=\operatorname{mex}([a_l,a_{l+1},\ldots,a_r])$, the array $a$ will become $[a_1,a_2,\ldots,a_{l-1},x,a_{r+1},a_{r+2},\ldots,a_{|a|}]$. Note that the length of $a$ decreases by $(r-l)$ after this operation. 26 27 Serval wants the final element in $a$ to be $0$. Help him! 28 29 More formally, you have to find a sequence of operations, such that after performing these operations in order, the length of $a$ becomes $1$, and the final element in $a$ is $0$. 30 31 It can be shown that at least one valid operation sequence exists under the constraints of the problem, and the length of any valid operation sequence does not exceed $n$. 32 33 Note that you do not need to minimize the number of operations. 34 35 $^{\text{∗}}$The minimum excluded (MEX) of a collection of integers $b_1, b_2, \ldots, b_k$ is defined as the smallest non-negative integer $x$ which does not occur in the collection $b$. 36 37 Input 38 39 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 1000$). The description of the test cases follows. 40 41 The first line of each test case contains a single integer $n$ ($4\le n\le 5000$) — the length of the array $a$. 42 43 The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0\le a_i\le n$) — the elements of the array $a$. 44 45 It is guaranteed that the sum of $n$ over all test cases does not exceed $5000$. 46 47 Output 48 49 For each test case, output a single integer $k$ ($0\le k\le n$) in the first line of output — the length of the operation sequence. 50 51 Then, output $k$ lines, the $i$-th line containing two integers $l_i$ and $r_i$ ($1\le l_i \lt r_i\le |a|$) — the two indices you choose in the $i$-th operation, where $|a|$ denotes the length of the array before this operation. 52 53 If there are multiple answers, you may print any of them. 54 55 Example 56 57 Input 58 59 ``` 60 6 61 62 4 63 64 1 2 3 4 65 66 5 67 68 0 1 0 0 1 69 70 6 71 72 0 0 0 0 0 0 73 74 6 75 76 5 4 3 2 1 0 77 78 4 79 80 0 0 1 1 81 82 4 83 84 1 0 0 0 85 ``` 86 87 Output 88 89 ``` 90 1 91 1 4 92 4 93 1 2 94 1 2 95 1 2 96 1 2 97 4 98 5 6 99 3 4 100 1 2 101 1 3 102 3 103 4 5 104 4 5 105 1 4 106 2 107 1 2 108 1 3 109 2 110 2 4 111 1 2 112 ``` 113 114 Note 115 116 In the first test case, since $\operatorname{mex}([1,2,3,4])=0$, after the only operation, the array becomes $[0]$. 117 118 In the second test case, the array $a$ changes as follows: $$ [\underline{0,1},0,0,1]\to [\underline{2,0},0,1]\to [\underline{1,0},1]\to [\underline{2,1}]\to [0]. $$ 119 120 In the third test case, the array $a$ changes as follows: $$ [0,0,0,0,\underline{0,0}]\to [0,0,\underline{0,0},1]\to [\underline{0,0},1,1]\to [\underline{1,1,1}]\to [0]. $$