codeforces-scrape

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

2147B.md (2049B)


      1 Source: https://codeforces.com/problemset/problem/2147/B
      2 
      3 B. Multiple Construction
      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 integer $n$. Your task is to construct an array of length $2 \cdot n$ such that:
     22 
     23 * Each integer from $1$ to $n$ appears exactly twice in the array.
     24 * For each integer $x$ ($1 \le x \le n$), the distance between the two occurrences of $x$ is a multiple of $x$. In other words, if $p_x$ and $q_x$ are the indices of the two occurrences of $x$, $| q_x - p_x |$ must be divisible by $x$.
     25 
     26 It can be shown that a solution always exists.
     27 
     28 Input
     29 
     30 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.
     31 
     32 Each of the next $t$ lines contains a single integer $n$ ($1 \le n \le 2 \cdot 10^{5}$).
     33 
     34 It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^{5}$.
     35 
     36 Output
     37 
     38 For each test case, print a line containing $2 \cdot n$ integers — the array that satisfies the given conditions.
     39 
     40 If there are multiple valid answers, print any of them.
     41 
     42 Example
     43 
     44 Input
     45 
     46 ```
     47 3
     48 2
     49 3
     50 1
     51 ```
     52 
     53 Output
     54 
     55 ```
     56 1 2 1 2
     57 1 3 1 2 3 2
     58 1 1
     59 ```
     60 
     61 Note
     62 
     63 [Visualizer link](https://codeforces.com/assets/contests/2147/B_RlbLXHyL5DuDqDlx4DG1.html)
     64 
     65 In the first test case:
     66 
     67 * The number $1$ appears at positions $1$ and $3$: the distance is $2$, which is divisible by $1$.
     68 * The number $2$ appears at positions $2$ and $4$: the distance is $2$, which is divisible by $2$.
     69 
     70 In the second test case:
     71 
     72 * The number $1$ appears at positions $1$ and $3$: the distance is $2$, which is divisible by $1$.
     73 * The number $2$ appears at positions $4$ and $6$: the distance is $2$, which is divisible by $2$.
     74 * The number $3$ appears at positions $2$ and $5$: the distance is $3$, which is divisible by $3$.
     75 
     76 In the third test case, the two occurrences of $1$ are at positions $1$ and $2$, so the distance between them is $1$, which is a multiple of $1$.