codeforces-scrape

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

1567B.md (1876B)


      1 Source: https://codeforces.com/problemset/problem/1567/B
      2 
      3 B. MEXor Mixup
      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 Alice gave Bob two integers $a$ and $b$ ($a \gt 0$ and $b \ge 0$). Being a curious boy, Bob wrote down an array of non-negative integers with $\operatorname{MEX}$ value of all elements equal to $a$ and $\operatorname{XOR}$ value of all elements equal to $b$.
     22 
     23 What is the shortest possible length of the array Bob wrote?
     24 
     25 Recall that the $\operatorname{MEX}$ ([Minimum EXcluded](https://en.wikipedia.org/wiki/Mex_(mathematics))) of an array is the minimum non-negative integer that does not belong to the array and the $\operatorname{XOR}$ of an array is the [bitwise XOR](https://en.wikipedia.org/wiki/Bitwise_operation#XOR) of all the elements of the array.
     26 
     27 Input
     28 
     29 The input consists of multiple test cases. The first line contains an integer $t$ ($1 \leq t \leq 5 \cdot 10^4$) — the number of test cases. The description of the test cases follows.
     30 
     31 The only line of each test case contains two integers $a$ and $b$ ($1 \leq a \leq 3 \cdot 10^5$; $0 \leq b \leq 3 \cdot 10^5$) — the $\operatorname{MEX}$ and $\operatorname{XOR}$ of the array, respectively.
     32 
     33 Output
     34 
     35 For each test case, output one (positive) integer — the length of the shortest array with $\operatorname{MEX}$ $a$ and $\operatorname{XOR}$ $b$. We can show that such an array always exists.
     36 
     37 Example
     38 
     39 Input
     40 
     41 ```
     42 5
     43 1 1
     44 2 1
     45 2 0
     46 1 10000
     47 2 10000
     48 ```
     49 
     50 Output
     51 
     52 ```
     53 3
     54 2
     55 3
     56 2
     57 3
     58 ```
     59 
     60 Note
     61 
     62 In the first test case, one of the shortest arrays with $\operatorname{MEX}$ $1$ and $\operatorname{XOR}$ $1$ is $[0, 2020, 2021]$.
     63 
     64 In the second test case, one of the shortest arrays with $\operatorname{MEX}$ $2$ and $\operatorname{XOR}$ $1$ is $[0, 1]$.
     65 
     66 It can be shown that these arrays are the shortest arrays possible.