codeforces-scrape

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

1630A.md (1889B)


      1 Source: https://codeforces.com/problemset/problem/1630/A
      2 
      3 A. And Matching
      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 a set of $n$ ($n$ is always a power of $2$) elements containing all integers $0, 1, 2, \ldots, n-1$ exactly once.
     22 
     23 Find $\frac{n}{2}$ pairs of elements such that:
     24 
     25 * Each element in the set is in exactly one pair.
     26 * The sum over all pairs of the [bitwise AND](https://en.wikipedia.org/wiki/Bitwise_operation#AND) of its elements must be exactly equal to $k$. Formally, if $a_i$ and $b_i$ are the elements of the $i$-th pair, then the following must hold: $$\sum_{i=1}^{n/2}{a_i \& b_i} = k,$$ where $\&$ denotes the bitwise AND operation.
     27 
     28 If there are many solutions, print any of them, if there is no solution, print $-1$ instead.
     29 
     30 Input
     31 
     32 The input consists of multiple test cases. The first line contains a single integer $t$ ($1 \leq t \leq 400$) — the number of test cases. Description of the test cases follows.
     33 
     34 Each test case consists of a single line with two integers $n$ and $k$ ($4 \leq n \leq 2^{16}$, $n$ is a power of $2$, $0 \leq k \leq n-1$).
     35 
     36 The sum of $n$ over all test cases does not exceed $2^{16}$. All test cases in each individual input will be pairwise different.
     37 
     38 Output
     39 
     40 For each test case, if there is no solution, print a single line with the integer $-1$.
     41 
     42 Otherwise, print $\frac{n}{2}$ lines, the $i$-th of them must contain $a_i$ and $b_i$, the elements in the $i$-th pair.
     43 
     44 If there are many solutions, print any of them. Print the pairs and the elements in the pairs in any order.
     45 
     46 Example
     47 
     48 Input
     49 
     50 ```
     51 4
     52 
     53 4 0
     54 
     55 4 1
     56 
     57 4 2
     58 
     59 4 3
     60 ```
     61 
     62 Output
     63 
     64 ```
     65 0 3
     66 1 2
     67 0 2
     68 1 3
     69 0 1
     70 2 3
     71 -1
     72 ```
     73 
     74 Note
     75 
     76 In the first test, $(0\&3)+(1\&2) = 0$.
     77 
     78 In the second test, $(0\&2)+(1\&3) = 1$.
     79 
     80 In the third test, $(0\&1)+(2\&3) = 2$.
     81 
     82 In the fourth test, there is no solution.