codeforces-scrape

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

2037C.md (1980B)


      1 Source: https://codeforces.com/problemset/problem/2037/C
      2 
      3 C. Superultra's Favorite Permutation
      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 Superultra, a little red panda, desperately wants primogems. In his dreams, a voice tells him that he must solve the following task to obtain a lifetime supply of primogems. Help Superultra!
     22 
     23 Construct a permutation$^{\text{∗}}$ $p$ of length $n$ such that $p_i + p_{i+1}$ is composite$^{\text{†}}$ over all $1 \leq i \leq n - 1$. If it's not possible, output $-1$.
     24 
     25 $^{\text{∗}}$A permutation of length $n$ is an array consisting of $n$ distinct integers from $1$ to $n$ in arbitrary order. For example, $[2,3,1,5,4]$ is a permutation, but $[1,2,2]$ is not a permutation ($2$ appears twice in the array), and $[1,3,4]$ is also not a permutation ($n=3$ but there is $4$ in the array).
     26 
     27 $^{\text{†}}$An integer $x$ is composite if it has at least one other divisor besides $1$ and $x$. For example, $4$ is composite because $2$ is a divisor.
     28 
     29 Input
     30 
     31 The first line contains $t$ ($1 \leq t \leq 10^4$) — the number of test cases.
     32 
     33 Each test case contains an integer $n$ ($2 \leq n \leq 2 \cdot 10^5$) — the length of the permutation.
     34 
     35 It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.
     36 
     37 Output
     38 
     39 For each test case, if it's not possible to construct $p$, output $-1$ on a new line. Otherwise, output $n$ integers $p_1, p_2, \ldots, p_n$ on a new line.
     40 
     41 Example
     42 
     43 Input
     44 
     45 ```
     46 2
     47 
     48 3
     49 
     50 8
     51 ```
     52 
     53 Output
     54 
     55 ```
     56 -1
     57 1 8 7 3 6 2 4 5
     58 ```
     59 
     60 Note
     61 
     62 In the first example, it can be shown that all permutation of size $3$ contain two adjacent elements whose sum is prime. For example, in the permutation $[2,3,1]$ the sum $2+3=5$ is prime.
     63 
     64 In the second example, we can verify that the sample output is correct because $1+8$, $8+7$, $7+3$, $3+6$, $6+2$, $2+4$, and $4+5$ are all composite. There may be other constructions that are correct.