codeforces-scrape

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

2162C.md (1912B)


      1 Source: https://codeforces.com/problemset/problem/2162/C
      2 
      3 C. Beautiful XOR
      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 integers $a$ and $b$. You are allowed to perform the following operation any number of times (including zero):
     22 
     23 * choose any integer $x$ such that $0 \le x \le a$ (the current value of $a$, not initial),
     24 * set $a := a \oplus x$. Here, $\oplus$ represents the [bitwise XOR](https://en.wikipedia.org/wiki/Bitwise_operation#XOR) operator.
     25 
     26 After performing a sequence of operations, you want the value of $a$ to become exactly $b$.
     27 
     28 Find a sequence of at most $100$ operations (values of $x$ used in each operation) that transforms $a$ into $b$, or report that it is impossible.
     29 
     30 Note that you are not required to find the minimum number of operations, but any valid sequence of at most $100$ operations.
     31 
     32 Input
     33 
     34 The first line of input contains a single integer $t$ ($1 \le t \le 1000$) — the number of test cases.
     35 
     36 Each test case contains two integers $a$ and $b$ ($1 \le a, b \le 10^9$).
     37 
     38 Output
     39 
     40 For each test case, if it is impossible to obtain $b$ from $a$ using the allowed operations, print a single line containing $-1$.
     41 
     42 Otherwise, on the first line print a single integer $k$ ($0 \le k \le 100$) — the number of operations. On the second line print $k$ integers ($x_1, x_2, \dots , x_k$) — the chosen values of $x$ in the order you apply them.
     43 
     44 If there are multiple valid sequences, you may print any one of them.
     45 
     46 Example
     47 
     48 Input
     49 
     50 ```
     51 6
     52 
     53 9 6
     54 
     55 13 13
     56 
     57 292 929
     58 
     59 405 400
     60 
     61 998 244
     62 
     63 244 353
     64 ```
     65 
     66 Output
     67 
     68 ```
     69 2
     70 
     71 7 8
     72 
     73 0
     74 
     75 -1
     76 
     77 1
     78 
     79 5
     80 
     81 2
     82 
     83 25 779
     84 
     85 -1
     86 ```
     87 
     88 Note
     89 
     90 For the first test case,
     91 
     92 * choose $x = 7$, now $a$ becomes equal to $9 \oplus 7 = 14$.
     93 * choose $x = 8$, now $a$ becomes equal to $14 \oplus 8 = 6$.
     94 
     95 Thus, we can make $a = b$.
     96 
     97 For the fourth test case, choosing $x = 5$ makes $a = b$.