codeforces-scrape

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

1981B.md (1477B)


      1 Source: https://codeforces.com/problemset/problem/1981/B
      2 
      3 B. Turtle and an Infinite Sequence
      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 There is a sequence $a_0, a_1, a_2, \ldots$ of infinite length. Initially $a_i = i$ for every non-negative integer $i$.
     22 
     23 After every second, each element of the sequence will simultaneously change. $a_i$ will change to $a_{i - 1} \mid a_i \mid a_{i + 1}$ for every positive integer $i$. $a_0$ will change to $a_0 \mid a_1$. Here, $|$ denotes [bitwise OR](https://en.wikipedia.org/wiki/Bitwise_operation#OR).
     24 
     25 Turtle is asked to find the value of $a_n$ after $m$ seconds. In particular, if $m = 0$, then he needs to find the initial value of $a_n$. He is tired of calculating so many values, so please help him!
     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 two integers $n, m$ ($0 \le n, m \le 10^9$).
     32 
     33 Output
     34 
     35 For each test case, output a single integer — the value of $a_n$ after $m$ seconds.
     36 
     37 Example
     38 
     39 Input
     40 
     41 ```
     42 9
     43 
     44 0 0
     45 
     46 0 1
     47 
     48 0 2
     49 
     50 1 0
     51 
     52 5 2
     53 
     54 10 1
     55 
     56 20 3
     57 
     58 1145 14
     59 
     60 19198 10
     61 ```
     62 
     63 Output
     64 
     65 ```
     66 0
     67 1
     68 3
     69 1
     70 7
     71 11
     72 23
     73 1279
     74 19455
     75 ```
     76 
     77 Note
     78 
     79 After $1$ second, $[a_0, a_1, a_2, a_3, a_4, a_5]$ will become $[1, 3, 3, 7, 7, 7]$.
     80 
     81 After $2$ seconds, $[a_0, a_1, a_2, a_3, a_4, a_5]$ will become $[3, 3, 7, 7, 7, 7]$.