codeforces-scrape

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

1918C.md (1515B)


      1 Source: https://codeforces.com/problemset/problem/1918/C
      2 
      3 C. XOR-distance
      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 You are given integers $a$, $b$, $r$. Find the smallest value of $|({a \oplus x}) - ({b \oplus x})|$ among all $0 \leq x \leq r$.
     22 
     23 $\oplus$ is the operation of [bitwise XOR](https://en.wikipedia.org/wiki/Bitwise_operation#XOR), and $|y|$ is [absolute value](https://en.wikipedia.org/wiki/Absolute_value) of $y$.
     24 
     25 Input
     26 
     27 The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases.
     28 
     29 Each test case contains integers $a$, $b$, $r$ ($0 \le a, b, r \le 10^{18}$).
     30 
     31 Output
     32 
     33 For each test case, output a single number — the smallest possible value.
     34 
     35 Example
     36 
     37 Input
     38 
     39 ```
     40 10
     41 
     42 4 6 0
     43 
     44 0 3 2
     45 
     46 9 6 10
     47 
     48 92 256 23
     49 
     50 165 839 201
     51 
     52 1 14 5
     53 
     54 2 7 2
     55 
     56 96549 34359 13851
     57 
     58 853686404475946 283666553522252166 127929199446003072
     59 
     60 735268590557942972 916721749674600979 895150420120690183
     61 ```
     62 
     63 Output
     64 
     65 ```
     66 2
     67 1
     68 1
     69 164
     70 542
     71 5
     72 3
     73 37102
     74 27934920819538516
     75 104449824168870225
     76 ```
     77 
     78 Note
     79 
     80 In the first test, when $r = 0$, then $x$ is definitely equal to $0$, so the answer is $|{4 \oplus 0} - {6 \oplus 0}| = |4 - 6| = 2$.
     81 
     82 In the second test:
     83 
     84 * When $x = 0$, $|{0 \oplus 0} - {3 \oplus 0}| = |0 - 3| = 3$.
     85 * When $x = 1$, $|{0 \oplus 1} - {3 \oplus 1}| = |1 - 2| = 1$.
     86 * When $x = 2$, $|{0 \oplus 2} - {3 \oplus 2}| = |2 - 1| = 1$.
     87 
     88 Therefore, the answer is $1$.
     89 
     90 In the third test, the minimum is achieved when $x = 1$.