codeforces-scrape

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

1003D.md (1641B)


      1 Source: https://codeforces.com/problemset/problem/1003/D
      2 
      3 D. Coins and Queries
      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 Polycarp has $n$ coins, the value of the $i$-th coin is $a_i$. It is guaranteed that all the values are integer powers of $2$ (i.e. $a_i = 2^d$ for some non-negative integer number $d$).
     22 
     23 Polycarp wants to know answers on $q$ queries. The $j$-th query is described as integer number $b_j$. The answer to the query is the minimum number of coins that is necessary to obtain the value $b_j$ using some subset of coins (Polycarp can use only coins he has). If Polycarp can't obtain the value $b_j$, the answer to the $j$-th query is -1.
     24 
     25 The queries are independent (the answer on the query doesn't affect Polycarp's coins).
     26 
     27 Input
     28 
     29 The first line of the input contains two integers $n$ and $q$ ($1 \le n, q \le 2 \cdot 10^5$) — the number of coins and the number of queries.
     30 
     31 The second line of the input contains $n$ integers $a_1, a_2, \dots, a_n$ — values of coins ($1 \le a_i \le 2 \cdot 10^9$). It is guaranteed that all $a_i$ are integer powers of $2$ (i.e. $a_i = 2^d$ for some non-negative integer number $d$).
     32 
     33 The next $q$ lines contain one integer each. The $j$-th line contains one integer $b_j$ — the value of the $j$-th query ($1 \le b_j \le 10^9$).
     34 
     35 Output
     36 
     37 Print $q$ integers $ans_j$. The $j$-th integer must be equal to the answer on the $j$-th query. If Polycarp can't obtain the value $b_j$ the answer to the $j$-th query is -1.
     38 
     39 Example
     40 
     41 Input
     42 
     43 ```
     44 5 4  
     45 2 4 8 2 4  
     46 8  
     47 5  
     48 14  
     49 10
     50 ```
     51 
     52 Output
     53 
     54 ```
     55 1  
     56 -1  
     57 3  
     58 2
     59 ```