codeforces-scrape

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

437B.md (1624B)


      1 Source: https://codeforces.com/problemset/problem/437/B
      2 
      3 B. The Child and Set
      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 stdin
     16 
     17 output
     18 
     19 stdout
     20 
     21 At the children's day, the child came to Picks's house, and messed his house up. Picks was angry at him. A lot of important things were lost, in particular the favorite set of Picks.
     22 
     23 Fortunately, Picks remembers something about his set *S*:
     24 
     25 * its elements were distinct integers from 1 to *limit*;
     26 * the value of ![](https://espresso.codeforces.com/dbdbeec11e8b492563da65b3e453ae26fd50a6f4.png) was equal to *sum*; here *lowbit*(*x*) equals 2*k* where *k* is the position of the first one in the binary representation of *x*. For example, *lowbit*(100102) = 102, *lowbit*(100012) = 12, *lowbit*(100002) = 100002 (binary representation).
     27 
     28 Can you help Picks and find any set *S*, that satisfies all the above conditions?
     29 
     30 Input
     31 
     32 The first line contains two integers: *sum*, *limit* (1 ≤ *sum*, *limit* ≤ 105).
     33 
     34 Output
     35 
     36 In the first line print an integer *n* (1 ≤ *n* ≤ 105), denoting the size of *S*. Then print the elements of set *S* in any order. If there are multiple answers, print any of them.
     37 
     38 If it's impossible to find a suitable set, print -1.
     39 
     40 Examples
     41 
     42 Input
     43 
     44 ```
     45 5 5
     46 ```
     47 
     48 Output
     49 
     50 ```
     51 2  
     52 4 5
     53 ```
     54 
     55 Input
     56 
     57 ```
     58 4 3
     59 ```
     60 
     61 Output
     62 
     63 ```
     64 3  
     65 2 3 1
     66 ```
     67 
     68 Input
     69 
     70 ```
     71 5 1
     72 ```
     73 
     74 Output
     75 
     76 ```
     77 -1
     78 ```
     79 
     80 Note
     81 
     82 In sample test 1: *lowbit*(4) = 4, *lowbit*(5) = 1, 4 + 1 = 5.
     83 
     84 In sample test 2: *lowbit*(1) = 1, *lowbit*(2) = 2, *lowbit*(3) = 1, 1 + 2 + 1 = 4.