codeforces-scrape

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

1225C.md (2263B)


      1 Source: https://codeforces.com/problemset/problem/1225/C
      2 
      3 C. p-binary
      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 Vasya will fancy any number as long as it is an integer power of two. Petya, on the other hand, is very conservative and only likes a single integer $p$ (which may be positive, negative, or zero). To combine their tastes, they invented $p$-binary numbers of the form $2^x + p$, where $x$ is a non-negative integer.
     22 
     23 For example, some $-9$-binary ("minus nine" binary) numbers are: $-8$ (minus eight), $7$ and $1015$ ($-8=2^0-9$, $7=2^4-9$, $1015=2^{10}-9$).
     24 
     25 The boys now use $p$-binary numbers to represent everything. They now face a problem: given a positive integer $n$, what's the smallest number of $p$-binary numbers (not necessarily distinct) they need to represent $n$ as their sum? It may be possible that representation is impossible altogether. Help them solve this problem.
     26 
     27 For example, if $p=0$ we can represent $7$ as $2^0 + 2^1 + 2^2$.
     28 
     29 And if $p=-9$ we can represent $7$ as one number $(2^4-9)$.
     30 
     31 Note that negative $p$-binary numbers are allowed to be in the sum (see the Notes section for an example).
     32 
     33 Input
     34 
     35 The only line contains two integers $n$ and $p$ ($1 \leq n \leq 10^9$, $-1000 \leq p \leq 1000$).
     36 
     37 Output
     38 
     39 If it is impossible to represent $n$ as the sum of any number of $p$-binary numbers, print a single integer $-1$. Otherwise, print the smallest possible number of summands.
     40 
     41 Examples
     42 
     43 Input
     44 
     45 ```
     46 24 0
     47 ```
     48 
     49 Output
     50 
     51 ```
     52 2
     53 ```
     54 
     55 Input
     56 
     57 ```
     58 24 1
     59 ```
     60 
     61 Output
     62 
     63 ```
     64 3
     65 ```
     66 
     67 Input
     68 
     69 ```
     70 24 -1
     71 ```
     72 
     73 Output
     74 
     75 ```
     76 4
     77 ```
     78 
     79 Input
     80 
     81 ```
     82 4 -7
     83 ```
     84 
     85 Output
     86 
     87 ```
     88 2
     89 ```
     90 
     91 Input
     92 
     93 ```
     94 1 1
     95 ```
     96 
     97 Output
     98 
     99 ```
    100 -1
    101 ```
    102 
    103 Note
    104 
    105 $0$-binary numbers are just regular binary powers, thus in the first sample case we can represent $24 = (2^4 + 0) + (2^3 + 0)$.
    106 
    107 In the second sample case, we can represent $24 = (2^4 + 1) + (2^2 + 1) + (2^0 + 1)$.
    108 
    109 In the third sample case, we can represent $24 = (2^4 - 1) + (2^2 - 1) + (2^2 - 1) + (2^2 - 1)$. Note that repeated summands are allowed.
    110 
    111 In the fourth sample case, we can represent $4 = (2^4 - 7) + (2^1 - 7)$. Note that the second summand is negative, which is allowed.
    112 
    113 In the fifth sample case, no representation is possible.