codeforces-scrape

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

1840B.md (1533B)


      1 Source: https://codeforces.com/problemset/problem/1840/B
      2 
      3 B. Binary Cafe
      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 Once upon a time, Toma found himself in a binary cafe. It is a very popular and unusual place.
     22 
     23 The cafe offers visitors $k$ different delicious desserts. The desserts are numbered from $0$ to $k-1$. The cost of the $i$-th dessert is $2^i$ coins, because it is a binary cafe! Toma is willing to spend no more than $n$ coins on tasting desserts. At the same time, he is not interested in buying any dessert more than once, because one is enough to evaluate the taste.
     24 
     25 In how many different ways can he buy several desserts (possibly zero) for tasting?
     26 
     27 Input
     28 
     29 The first line of the input contains a single integer $t$ ($1 \le t \le 1000$) — the number of test cases.
     30 
     31 Then follows $t$ lines, each of which describes one test case.
     32 
     33 Each test case is given on a single line and consists of two integers $n$ and $k$ ($1 \le n, k \le 10^9$) — the number of coins Toma is willing to spend and the number of desserts in the binary cafe.
     34 
     35 Output
     36 
     37 Output $t$ integers, the $i$-th of which should be equal to the answer for the $i$-th test case — the number of ways to buy desserts for tasting.
     38 
     39 Example
     40 
     41 Input
     42 
     43 ```
     44 5
     45 
     46 1 2
     47 
     48 2 1
     49 
     50 2 2
     51 
     52 10 2
     53 
     54 179 100
     55 ```
     56 
     57 Output
     58 
     59 ```
     60 2
     61 2
     62 3
     63 4
     64 180
     65 ```
     66 
     67 Note
     68 
     69 Variants for 1st sample: {}, {1}
     70 
     71 Variants for 2nd sample: {}, {1}
     72 
     73 Variants for 3rd sample: {}, {1}, {2}
     74 
     75 Variants for 4th sample: {}, {1}, {2}, {1, 2}