codeforces-scrape

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

1632C.md (1846B)


      1 Source: https://codeforces.com/problemset/problem/1632/C
      2 
      3 C. Strange Test
      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 Igor is in 11th grade. Tomorrow he will have to write an informatics test by the strictest teacher in the school, Pavel Denisovich.
     22 
     23 Igor knows how the test will be conducted: first of all, the teacher will give each student two positive integers $a$ and $b$ ($a \lt b$). After that, the student can apply any of the following operations any number of times:
     24 
     25 * $a := a + 1$ (increase $a$ by $1$),
     26 * $b := b + 1$ (increase $b$ by $1$),
     27 * $a := a \ | \ b$ (replace $a$ with the [bitwise OR](https://en.wikipedia.org/wiki/Bitwise_operation#OR) of $a$ and $b$).
     28 
     29 To get full marks on the test, the student has to tell the teacher the minimum required number of operations to make $a$ and $b$ equal.
     30 
     31 Igor already knows which numbers the teacher will give him. Help him figure out what is the minimum number of operations needed to make $a$ equal to $b$.
     32 
     33 Input
     34 
     35 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). Description of the test cases follows.
     36 
     37 The only line for each test case contains two integers $a$ and $b$ ($1 \le a \lt b \le 10^6$).
     38 
     39 It is guaranteed that the sum of $b$ over all test cases does not exceed $10^6$.
     40 
     41 Output
     42 
     43 For each test case print one integer — the minimum required number of operations to make $a$ and $b$ equal.
     44 
     45 Example
     46 
     47 Input
     48 
     49 ```
     50 5
     51 1 3
     52 5 8
     53 2 5
     54 3 19
     55 56678 164422
     56 ```
     57 
     58 Output
     59 
     60 ```
     61 1
     62 3
     63 2
     64 1
     65 23329
     66 ```
     67 
     68 Note
     69 
     70 In the first test case, it is optimal to apply the third operation.
     71 
     72 In the second test case, it is optimal to apply the first operation three times.
     73 
     74 In the third test case, it is optimal to apply the second operation and then the third operation.