codeforces-scrape

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

2160C.md (1537B)


      1 Source: https://codeforces.com/problemset/problem/2160/C
      2 
      3 C. Reverse 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 Given a positive integer $x$, let $f(x)$ be the positive integer formed by reversing the binary representation of $x$ without leading zeroes. For example, if $x=12=1100_2$, then $f(x)=0011_2=3$.
     22 
     23 You are given an integer $n$. Please determine if there exists a positive integer $x$ such that $x \oplus f(x) = n$$^{\text{∗}}$.
     24 
     25 $^{\text{∗}}$Here, $\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 The first line of each test case contains an integer $n$ ($0 \leq n \lt 2^{30}$).
     32 
     33 Output
     34 
     35 For each test case, output YES if there exists a positive integer $x$ such that $x \oplus f(x) = n$, and NO otherwise.
     36 
     37 You can output the answer in any case. For example, the strings "yEs", "yes", and "Yes" are also recognized as positive responses.
     38 
     39 Example
     40 
     41 Input
     42 
     43 ```
     44 6
     45 
     46 0
     47 
     48 3
     49 
     50 6
     51 
     52 8
     53 
     54 10
     55 
     56 11
     57 ```
     58 
     59 Output
     60 
     61 ```
     62 YES
     63 
     64 YES
     65 
     66 YES
     67 
     68 NO
     69 
     70 YES
     71 
     72 NO
     73 ```
     74 
     75 Note
     76 
     77 In the first case, when $x=1$, $f(x)=1$, and $x \oplus f(x)=0$. Thus, the answer is YES.
     78 
     79 In the second case, when $x=2$, $f(x)=1$, and $x \oplus f(x)=3$. Thus, the answer is YES.
     80 
     81 In the fourth test case, we can show there is no $x$ that satisfies $x \oplus f(x)=8$, so the answer is NO.