codeforces-scrape

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

1744D.md (2376B)


      1 Source: https://codeforces.com/problemset/problem/1744/D
      2 
      3 D. Divisibility by 2^n
      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 You are given an array of positive integers $a_1, a_2, \ldots, a_n$.
     22 
     23 Make the product of all the numbers in the array (that is, $a_1 \cdot a_2 \cdot \ldots \cdot a_n$) divisible by $2^n$.
     24 
     25 You can perform the following operation as many times as you like:
     26 
     27 * select an arbitrary index $i$ ($1 \leq i \leq n$) and replace the value $a_i$ with $a_i=a_i \cdot i$.
     28 
     29 You cannot apply the operation repeatedly to a single index. In other words, all selected values of $i$ must be different.
     30 
     31 Find the smallest number of operations you need to perform to make the product of all the elements in the array divisible by $2^n$. Note that such a set of operations does not always exist.
     32 
     33 Input
     34 
     35 The first line of the input contains a single integer $t$ $(1 \leq t \leq 10^4$) — the number test cases.
     36 
     37 Then the descriptions of the input data sets follow.
     38 
     39 The first line of each test case contains a single integer $n$ ($1 \leq n \leq 2 \cdot 10^5$) — the length of array $a$.
     40 
     41 The second line of each test case contains exactly $n$ integers: $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq 10^9$).
     42 
     43 It is guaranteed that the sum of $n$ values over all test cases in a test does not exceed $2 \cdot 10^5$.
     44 
     45 Output
     46 
     47 For each test case, print the least number of operations to make the product of all numbers in the array divisible by $2^n$. If the answer does not exist, print -1.
     48 
     49 Example
     50 
     51 Input
     52 
     53 ```
     54 6
     55 
     56 1
     57 
     58 2
     59 
     60 2
     61 
     62 3 2
     63 
     64 3
     65 
     66 10 6 11
     67 
     68 4
     69 
     70 13 17 1 1
     71 
     72 5
     73 
     74 1 1 12 1 1
     75 
     76 6
     77 
     78 20 7 14 18 3 5
     79 ```
     80 
     81 Output
     82 
     83 ```
     84 0
     85 1
     86 1
     87 -1
     88 2
     89 1
     90 ```
     91 
     92 Note
     93 
     94 In the first test case, the product of all elements is initially $2$, so no operations needed.
     95 
     96 In the second test case, the product of elements initially equals $6$. We can apply the operation for $i = 2$, and then $a_2$ becomes $2\cdot2=4$, and the product of numbers becomes $3\cdot4=12$, and this product of numbers is divided by $2^n=2^2=4$.
     97 
     98 In the fourth test case, even if we apply all possible operations, we still cannot make the product of numbers divisible by $2^n$  — it will be $(13\cdot1)\cdot(17\cdot2)\cdot(1\cdot3)\cdot(1\cdot4)=5304$, which does not divide by $2^n=2^4=16$.
     99 
    100 In the fifth test case, we can apply operations for $i = 2$ and $i = 4$.