codeforces-scrape

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

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$.