codeforces-scrape

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

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