codeforces-scrape

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

2203C.md (1708B)


      1 Source: https://codeforces.com/problemset/problem/2203/C
      2 
      3 C. Test Generator
      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 You are developing a test generator. It takes two integers $s$ and $m$ as input. You need to construct an array of non-negative integers $a = [a_{1}, a_{2}, \dots, a_{n}]$ such that:
     22 
     23 1. $\displaystyle\sum_{i=1}^{n} a_i = s$;
     24 2. for each $i$, the condition $a_i \,\&\, m = a_i$ holds, where $\&$ denotes the bitwise AND operator.
     25 
     26 In other words, in each number $a_i$, the bits that are set to one can only be in the positions where the bits in the number $m$ are also set to one.
     27 
     28 Determine whether there exists at least one such array. If it exists, find the minimum possible length $n$.
     29 
     30 Input
     31 
     32 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.
     33 
     34 Each test case consists of a single line containing two integers $s$ and $m$ ($1 \le s, m \le 10^{18}$) — parameters of the generator.
     35 
     36 Output
     37 
     38 For each test case, print one integer:
     39 
     40 * if such an array does not exist, print $-1$;
     41 * otherwise, print the minimum possible value of $n$ — the length of the array.
     42 
     43 Example
     44 
     45 Input
     46 
     47 ```
     48 6
     49 
     50 13 5
     51 
     52 13 3
     53 
     54 13 6
     55 
     56 1000000007 2776648
     57 
     58 99999999999 1
     59 
     60 998244353 1557287
     61 ```
     62 
     63 Output
     64 
     65 ```
     66 3
     67 
     68 5
     69 
     70 -1
     71 
     72 -1
     73 
     74 99999999999
     75 
     76 642
     77 ```
     78 
     79 Note
     80 
     81 Let's analyze some examples:
     82 
     83 * For $s = 13, m = 5$, the answer is $3$, as there is a suitable array $a = [5, 4, 4]$;
     84 * For $s = 13, m = 3$, the answer is $5$, as there is a suitable array $a = [3, 3, 3, 3, 1]$;
     85 * For $s = 13, m = 6$, the answer is $-1$, as there is no suitable array.