1926E.md (2018B)
1 Source: https://codeforces.com/problemset/problem/1926/E 2 3 E. Vlad and an Odd Ordering 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 Vladislav has $n$ cards numbered $1, 2, \dots, n$. He wants to lay them down in a row as follows: 22 23 * First, he lays down all the odd-numbered cards from smallest to largest. 24 * Next, he lays down all cards that are twice an odd number from smallest to largest (i.e. $2$ multiplied by an odd number). 25 * Next, he lays down all cards that are $3$ times an odd number from smallest to largest (i.e. $3$ multiplied by an odd number). 26 * Next, he lays down all cards that are $4$ times an odd number from smallest to largest (i.e. $4$ multiplied by an odd number). 27 * And so on, until all cards are laid down. 28 29 What is the $k$-th card he lays down in this process? Once Vladislav puts a card down, he cannot use that card again. 30 31 Input 32 33 The first line contains an integer $t$ ($1 \leq t \leq 5 \cdot 10^4$) — the number of test cases. 34 35 The only line of each test case contains two integers $n$ and $k$ ($1 \leq k \leq n \leq 10^9$) — the number of cards Vlad has, and the position of the card you need to output. 36 37 Output 38 39 For each test case, output a single integer — the $k$-th card Vladislav lays down. 40 41 Example 42 43 Input 44 45 ``` 46 11 47 48 7 1 49 50 7 2 51 52 7 3 53 54 7 4 55 56 7 5 57 58 7 6 59 60 7 7 61 62 1 1 63 64 34 14 65 66 84 19 67 68 1000000000 1000000000 69 ``` 70 71 Output 72 73 ``` 74 1 75 3 76 5 77 7 78 2 79 6 80 4 81 1 82 27 83 37 84 536870912 85 ``` 86 87 Note 88 89 In the first seven test cases, $n=7$. Vladislav lays down the cards as follows: 90 91 * First — all the odd-numbered cards in the order $1$, $3$, $5$, $7$. 92 * Next — all cards that are twice an odd number in the order $2$, $6$. 93 * Next, there are no remaining cards that are $3$ times an odd number. (Vladislav has only one of each card.) 94 * Next — all cards that are $4$ times an odd number, and there is only one such card: $4$. 95 * There are no more cards left, so Vladislav stops. 96 97 Thus the order of cards is $1$, $3$, $5$, $7$, $2$, $6$, $4$.