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.