2074C.md (1754B)
1 Source: https://codeforces.com/problemset/problem/2074/C 2 3 C. XOR and Triangle 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 This time, the pink soldiers have given you an integer $x$ ($x \ge 2$). 22 23 Please determine if there exists a positive integer $y$ that satisfies the following conditions. 24 25 * $y$ is strictly less than $x$. 26 * There exists a non-degenerate triangle$^{\text{∗}}$ with side lengths $x$, $y$, $x \oplus y$. Here, $\oplus$ denotes the [bitwise XOR operation](https://en.wikipedia.org/wiki/Bitwise_operation#XOR). 27 28 Additionally, if there exists such an integer $y$, output any. 29 30 $^{\text{∗}}$A triangle with side lengths $a$, $b$, $c$ is non-degenerate when $a+b \gt c$, $a+c \gt b$, $b+c \gt a$. 31 32 Input 33 34 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 2000$). The description of the test cases follows. 35 36 The only line of each test case contains a single integer $x$ ($2 \le x \le 10^9$). 37 38 Output 39 40 For each test case, print one integer on a separate line. The integer you must output is as follows: 41 42 * If there exists an integer $y$ satisfying the conditions, output the value of $y$ ($1 \le y \lt x$); 43 * Otherwise, output $-1$. 44 45 If there exist multiple integers that satisfy the conditions, you may output any. 46 47 Example 48 49 Input 50 51 ``` 52 7 53 54 5 55 56 2 57 58 6 59 60 3 61 62 69 63 64 4 65 66 420 67 ``` 68 69 Output 70 71 ``` 72 3 73 -1 74 5 75 -1 76 66 77 -1 78 320 79 ``` 80 81 Note 82 83 In the first test case, there exists a non-degenerate triangle with side lengths $3$, $5$, and $3 \oplus 5 = 6$. Therefore, $y=3$ is a valid answer. 84 85 In the second test case, $1$ is the only possible candidate for $y$, but it cannot make a non-degenerate triangle. Therefore, the answer is $-1$.