Vlad and an Odd Ordering (Codeforces 1926E)
Tags: Math, bitmasks

Vladislav has $$$n$$$ cards numbered $$$1, 2, \dots, n$$$. He wants to lay them down in a row as follows:   First, he lays down all the odd-numbered cards from smallest to largest.  Next, he lays down all cards that are twice an odd number from smallest to largest (i.e. $$$2$$$ multiplied by an odd number).  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).  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).  And so on, until all cards are laid down.  What is the $$$k$$$-th card he lays down in this process? Once Vladislav puts a card down, he cannot use that card again.

Input: The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 5 \cdot 10^4$$$) — the number of test cases.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.

Output: For each test case, output a single integer — the $$$k$$$-th card Vladislav lays down.

Note: In the first seven test cases, $$$n=7$$$. Vladislav lays down the cards as follows:   First — all the odd-numbered cards in the order $$$1$$$, $$$3$$$, $$$5$$$, $$$7$$$.  Next — all cards that are twice an odd number in the order $$$2$$$, $$$6$$$.  Next, there are no remaining cards that are $$$3$$$ times an odd number. (Vladislav has only one of each card.)  Next — all cards that are $$$4$$$ times an odd number, and there is only one such card: $$$4$$$.  There are no more cards left, so Vladislav stops.  Thus the order of cards is $$$1$$$, $$$3$$$, $$$5$$$, $$$7$$$, $$$2$$$, $$$6$$$, $$$4$$$.

Sample Inputs:
11
7 1
7 2
7 3
7 4
7 5
7 6
7 7
1 1
34 14
84 19
1000000000 1000000000

Sample Outputs:
1
3
5
7
2
6
4
1
27
37
536870912

Solution (Python):
from math import *
import sys, io, os, time
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
ii = lambda : int(input())
mi = lambda : map(int, input().split())
li = lambda : list(mi())
ls = lambda : list(map(str, input().split()))
MOD = 10 ** 9 + 7

def MainProg(n, k):
    odd = (n + 1) // 2
    if k <= odd:
        return 2 * k - 1
    k -= odd
    num = 2
    while k > 0:
        m = n // num - n // (num * 2)
        if k <= m:
            return num * (2 * k - 1)
        k -= m
        num *= 2
    return -1

def solve():
    (n, k) = map(int, input().split())
    print(MainProg(n, k))

def main():
    startTime = time.time()
    test_numbers = 1
    test_numbers = ii()
    for testcase in range(test_numbers):
        solve()
    print('Time: {} ms'.format(int((time.time() - startTime) * 1000)), file=sys.stderr)
main()

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()

def solve():
    (n, k) = map(int, input().split())
    mod = 1
    next = (n + mod) // (2 * mod)
    while k > next:
        k -= next
        mod *= 2
        next = (n + mod) // (2 * mod)
    ans = k * (2 * mod) - mod
    print(ans)
    return
T = int(input())
for _ in range(T):
    solve()

Solution (Python):
from math import *
import sys, io, os, time
input = sys.stdin.readline
ii = lambda : int(input())
mi = lambda : map(int, input().split())
li = lambda : list(mi())
ls = lambda : list(map(str, input().split()))
MOD = 10 ** 9 + 7

def MainProg(n, k):
    odd = (n + 1) // 2
    if k <= odd:
        return 2 * k - 1
    k -= odd
    num = 2
    while k > 0:
        m = n // num - n // (num * 2)
        if k <= m:
            return num * (2 * k - 1)
        k -= m
        num *= 2
    return -1

def solve():
    (n, k) = map(int, input().split())
    print(MainProg(n, k))

def main():
    startTime = time.time()
    test_numbers = 1
    test_numbers = ii()
    for testcase in range(test_numbers):
        solve()
    print('Time: {} ms'.format(int((time.time() - startTime) * 1000)), file=sys.stderr)
main()