codeforces-scrape

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

1788C.md (1636B)


      1 Source: https://codeforces.com/problemset/problem/1788/C
      2 
      3 C. Matching Numbers
      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$. Pair the integers $1$ to $2n$ (i.e. each integer should be in exactly one pair) so that each sum of matched pairs is consecutive and distinct.
     22 
     23 Formally, let $(a_i, b_i)$ be the pairs that you matched. $\{a_1, b_1, a_2, b_2, \ldots, a_n, b_n\}$ should be a permutation of $\{1, 2, \ldots, 2n\}$. Let the sorted list of $\{a_1+b_1, a_2+b_2, \ldots, a_n+b_n\}$ be $s_1 \lt s_2 \lt \ldots \lt s_n$. We must have $s_{i+1}-s_i = 1$ for $1 \le i \le n - 1$.
     24 
     25 Input
     26 
     27 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 500$). The description of the test cases follows.
     28 
     29 For each test case, a single integer $n$ ($1 \leq n \leq 10^5$) is given.
     30 
     31 It is guaranteed that the sum of $n$ over all test cases doesn't exceed $10^5$.
     32 
     33 Output
     34 
     35 For each test case, if it is impossible to make such a pairing, print "No".
     36 
     37 Otherwise, print "Yes" followed by $n$ lines.
     38 
     39 At each line, print two integers that are paired.
     40 
     41 You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.
     42 
     43 If there are multiple solutions, print any.
     44 
     45 Example
     46 
     47 Input
     48 
     49 ```
     50 4
     51 1
     52 2
     53 3
     54 4
     55 ```
     56 
     57 Output
     58 
     59 ```
     60 Yes
     61 1 2
     62 No
     63 Yes
     64 1 6
     65 3 5
     66 4 2
     67 No
     68 ```
     69 
     70 Note
     71 
     72 For the third test case, each integer from $1$ to $6$ appears once. The sums of matched pairs are $4+2=6$, $1+6=7$, and $3+5=8$, which are consecutive and distinct.