codeforces-scrape

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

1958C.md (1915B)


      1 Source: https://codeforces.com/problemset/problem/1958/C
      2 
      3 C. Firewood
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 512 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 It's pretty cold in Berland (yes, even in May). So Monocarp has to light his fireplace.
     22 
     23 Monocarp has a big log of wood, which weighs $2^n$ grams. Monocarp has watched the weather forecast and decided that he has to burn $k$ grams of wood in the fireplace today, and the remaining $2^n-k$ grams of wood will be used tomorrow.
     24 
     25 In one minute, Monocarp can use his saw to split one of his logs in half. Initially he has only one log, but of course, after splitting a log, he gets two new logs. If the weight of the log is $x$, then each of the resulting logs has weight equal to $\frac{x}{2}$. Monocarp can't split logs of weight $1$ gram.
     26 
     27 Monocarp has to cut his log in such a way that some of the resulting logs weigh exactly $k$ grams in total (and since the total weight of wood doesn't change, the remaining logs will have a total weight equal to exactly $2^n-k$). Help him to calculate the minimum number of minutes he has to spend cutting the logs.
     28 
     29 Input
     30 
     31 The first line contains one integer $t$ ($1 \le t \le 10^4$) — the number of test cases.
     32 
     33 Each test case consists of one line containing two integers $n$ and $k$ ($1 \le n \le 60$; $1 \le k \le 2^n-1$).
     34 
     35 Output
     36 
     37 For each test case, print one integer — the minimum number of minutes Monocarp has to spend splitting the wood.
     38 
     39 Example
     40 
     41 Input
     42 
     43 ```
     44 4
     45 
     46 2 2
     47 
     48 2 1
     49 
     50 10 3
     51 
     52 50 36679020707840
     53 ```
     54 
     55 Output
     56 
     57 ```
     58 1
     59 2
     60 10
     61 16
     62 ```
     63 
     64 Note
     65 
     66 In the first test case, Monocarp has to cut his log exactly once. Then he will have two logs weighing $2$ grams each.
     67 
     68 In the second test case, Monocarp has to cut his log of $4$ grams once, then cut one of the resulting logs. He will have one log of weight $2$ and two logs of weight $1$, so he can use two logs to get exactly $3$ grams.