codeforces-scrape

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

2108B.md (1835B)


      1 Source: https://codeforces.com/problemset/problem/2108/B
      2 
      3 B. SUMdamental Decomposition
      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 On a recent birthday, your best friend Maurice gave you a pair of numbers $n$ and $x$, and asked you to construct an array of positive numbers $a$ of length $n$ such that $a_1 \oplus a_2 \oplus \cdots \oplus a_n = x$ $^{\text{∗}}$.
     22 
     23 This task seemed too simple to you, and therefore you decided to give Maurice a return gift by constructing an array among all such arrays that has the smallest sum of its elements. You immediately thought of a suitable array; however, since writing it down turned out to be too time-consuming, Maurice will have to settle for just the sum of its elements.
     24 
     25 $^{\text{∗}}$$\oplus$ denotes the [bitwise XOR operation](https://en.wikipedia.org/wiki/Bitwise_operation#XOR).
     26 
     27 Input
     28 
     29 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.
     30 
     31 Each test case consists of a single line containing a pair of numbers $n$ and $x$ ($1 \le n \le 10^9, \; 0 \le x \le 10^9$) — the numbers given to you by Maurice.
     32 
     33 Output
     34 
     35 For each test case, output your gift to Maurice — the sum of the elements of the array that satisfies all the described properties. If a suitable array does not exist, output $-1$.
     36 
     37 Example
     38 
     39 Input
     40 
     41 ```
     42 8
     43 
     44 2 1
     45 
     46 3 6
     47 
     48 1 0
     49 
     50 2 0
     51 
     52 5 0
     53 
     54 2 27
     55 
     56 15 43
     57 
     58 12345678 9101112
     59 ```
     60 
     61 Output
     62 
     63 ```
     64 5
     65 8
     66 -1
     67 2
     68 8
     69 27
     70 55
     71 21446778
     72 ```
     73 
     74 Note
     75 
     76 In the first test case, one of the suitable arrays is $[2, 3]$. It can be shown that it is impossible to achieve a smaller sum of array elements.
     77 
     78 In the second case, one of the suitable arrays is $[1, 3, 4]$. It can also be shown that this is the optimal amount.