codeforces-scrape

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

1957B.md (1754B)


      1 Source: https://codeforces.com/problemset/problem/1957/B
      2 
      3 B. A BIT of a Construction
      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 Given integers $n$ and $k$, construct a sequence of $n$ non-negative (i.e. $\geq 0$) integers $a_1, a_2, \ldots, a_n$ such that
     22 
     23 1. $\sum\limits_{i = 1}^n a_i = k$
     24 2. The number of $1$s in the binary representation of $a_1 | a_2 | \ldots | a_n$ is maximized, where $|$ denotes the [bitwise OR operation](https://en.wikipedia.org/wiki/Bitwise_operation#OR).
     25 
     26 Input
     27 
     28 The first line contains a single integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases.
     29 
     30 The only line of each test case contains two integers $n$ and $k$ ($1 \leq n \leq 2 \cdot 10^5$, $1 \leq k \leq 10^9$) — the number of non-negative integers to be printed and the sum respectively.
     31 
     32 It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.
     33 
     34 Output
     35 
     36 For each test case, output a sequence $a_1, a_2, \ldots, a_n$ on a new line that satisfies the conditions given above.
     37 
     38 If there are multiple solutions, print any of them.
     39 
     40 Example
     41 
     42 Input
     43 
     44 ```
     45 4
     46 
     47 1 5
     48 
     49 2 3
     50 
     51 2 5
     52 
     53 6 51
     54 ```
     55 
     56 Output
     57 
     58 ```
     59 5
     60 1 2
     61 5 0
     62 3 1 1 32 2 12
     63 ```
     64 
     65 Note
     66 
     67 In the first test case, we have to print exactly one integer, hence we can only output $5$ as the answer.
     68 
     69 In the second test case, we output $1, 2$ which sum up to $3$, and $1 | 2 = (11)_2$ has two $1$s in its binary representation, which is the maximum we can achieve in these constraints.
     70 
     71 In the fourth test case, we output $3, 1, 1, 32, 2, 12$ which sum up to $51$, and $3 | 1 | 1 | 32 | 2 | 12 = (101\,111)_2$ has five $1$s in its binary representation, which is the maximum we can achieve in these constraints.