codeforces-scrape

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

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]. $$