codeforces-scrape

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

2121D.md (3012B)


      1 Source: https://codeforces.com/problemset/problem/2121/D
      2 
      3 D. 1709
      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 You are given two arrays of integers $a_1, a_2, \ldots, a_n$ and $b_1, b_2, \ldots, b_n$. It is guaranteed that each integer from $1$ to $2 \cdot n$ appears in exactly one of the arrays.
     22 
     23 You need to perform a certain number of operations (possibly zero) so that both of the following conditions are satisfied:
     24 
     25 * For each $1 \leq i \lt n$, it holds that $a_i \lt a_{i + 1}$ and $b_i \lt b_{i + 1}$.
     26 * For each $1 \leq i \leq n$, it holds that $a_i \lt b_i$.
     27 
     28 During each operation, you can perform exactly one of the following three actions:
     29 
     30 1. Choose an index $1 \leq i \lt n$ and swap the values $a_i$ and $a_{i + 1}$.
     31 2. Choose an index $1 \leq i \lt n$ and swap the values $b_i$ and $b_{i + 1}$.
     32 3. Choose an index $1 \leq i \leq n$ and swap the values $a_i$ and $b_i$.
     33 
     34 You do not need to minimize the number of operations, but the total number must not exceed $1709$. Find any sequence of operations that satisfies both conditions.
     35 
     36 Input
     37 
     38 Each test consists of multiple test cases. The first line contains a single integer $t$ ($1 \leq t \leq 100$) — the number of test cases. The description of the test cases follows.
     39 
     40 The first line of each test case contains a single integer $n$ ($1 \leq n \leq 40$) — the length of the arrays $a$ and $b$.
     41 
     42 The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq 2 \cdot n$).
     43 
     44 The third line of each test case contains $n$ integers $b_1, b_2, \ldots, b_n$ ($1 \leq b_i \leq 2 \cdot n$).
     45 
     46 It is guaranteed that each integer from $1$ to $2 \cdot n$ appears either in array $a$ or in array $b$.
     47 
     48 Output
     49 
     50 For each test case, output the sequence of operations.
     51 
     52 In the first line for each test case, output the number of operations $k$. Note that $0 \leq k \leq 1709$.
     53 
     54 In the following $k$ lines for each test case, output the operations themselves:
     55 
     56 * If you want to swap the values $a_i$ and $a_{i + 1}$, output two integers $1$ and $i$. Note that $1 \leq i \lt n$.
     57 * If you want to swap the values $b_i$ and $b_{i + 1}$, output two integers $2$ and $i$. Note that $1 \leq i \lt n$.
     58 * If you want to swap the values $a_i$ and $b_i$, output two integers $3$ and $i$. Note that $1 \leq i \leq n$.
     59 
     60 It can be shown that under the given constraints, a solution always exists.
     61 
     62 Example
     63 
     64 Input
     65 
     66 ```
     67 6
     68 
     69 1
     70 
     71 1
     72 
     73 2
     74 
     75 1
     76 
     77 2
     78 
     79 1
     80 
     81 2
     82 
     83 1 3
     84 
     85 4 2
     86 
     87 2
     88 
     89 1 4
     90 
     91 3 2
     92 
     93 3
     94 
     95 6 5 4
     96 
     97 3 2 1
     98 
     99 3
    100 
    101 5 3 4
    102 
    103 2 6 1
    104 ```
    105 
    106 Output
    107 
    108 ```
    109 0
    110 1
    111 3 1
    112 1
    113 2 1
    114 1
    115 3 2
    116 9
    117 3 1
    118 3 2
    119 3 3
    120 1 1
    121 2 1
    122 2 2
    123 1 2
    124 1 1
    125 2 1
    126 6
    127 2 2
    128 1 1
    129 1 2
    130 2 1
    131 3 1
    132 3 2
    133 ```
    134 
    135 Note
    136 
    137 In the first test case, $a_1 \lt b_1$, so no operations need to be applied.
    138 
    139 In the second test case, $a_1 \gt b_1$. After applying the operation, these values will be swapped.
    140 
    141 In the third test case, after applying the operation, $a = [1, 3]$ and $b = [2, 4]$.
    142 
    143 In the fourth test case, after applying the operation, $a = [1, 2]$ and $b = [3, 4]$.