codeforces-scrape

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

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$.