2184C.md (2114B)
1 Source: https://codeforces.com/problemset/problem/2184/C 2 3 C. Huge Pile 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 Andrei has a huge pile of $n$ apples. He can divide the pile into two smaller piles: if there are $x$ apples in the pile, he will get piles with $\lfloor \frac{x}{2} \rfloor$$^{\text{∗}}$ and $\lceil \frac{x}{2} \rceil$$^{\text{†}}$ apples. This division takes Andrei $1$ minute. 22 23 Andrei wants to eat $k$ apples, but he doesn't want to count them at all. That is why he wants to obtain a pile that contains exactly $k$ apples. Determine whether it is possible to achieve this by performing pile divisions. If it is possible, find the minimum possible time for Andrei to obtain a pile with exactly $k$ apples. 24 25 $^{\text{∗}}$$\lfloor \frac{x}{2} \rfloor$ — the largest integer $\le \frac{x}{2}$. 26 27 $^{\text{†}}$$\lceil \frac{x}{2} \rceil$ — the smallest integer $\ge \frac{x}{2}$. 28 29 Input 30 31 Each test consists of several test cases. The first line contains a single integer $t$ $(1 \le t \le 10^4)$ — the number of test cases. The following lines describe the test cases. 32 33 In the only line of each test case, two integers $n$ and $k$ are given — the number of apples in the huge pile and the number of apples that Andrei wants to obtain in one pile $(1 \le n, k \le 10^9)$. 34 35 Output 36 37 For each test case, output $-1$ if it is impossible to obtain a pile with exactly $k$ apples. Otherwise, output the minimum possible time required to obtain such a pile. 38 39 Example 40 41 Input 42 43 ``` 44 4 45 46 10 3 47 48 11 5 49 50 21 4 51 52 1000000000 1 53 ``` 54 55 Output 56 57 ``` 58 2 59 60 1 61 62 -1 63 64 29 65 ``` 66 67 Note 68 69 In the first test case, after the first division, two piles of $5$ apples will be created. If one of them is divided, it will result in piles with $2$ and $3$ apples, so the answer is $2$. 70 71 In the second test case, if the pile is divided into two, it will result in piles with $5$ and $6$ apples, so the answer is $1$. 72 73 In the third test case, it is only possible to obtain piles with $1$, $2$, $3$, $5$, $6$, $10$, $11$, or $21$ apples, so the answer is $-1$.