codeforces-scrape

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

1676E.md (2852B)


      1 Source: https://codeforces.com/problemset/problem/1676/E
      2 
      3 E. Eating Queries
      4 
      5 time limit per test
      6 
      7 3.5 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 Timur has $n$ candies. The $i$-th candy has a quantity of sugar equal to $a_i$. So, by eating the $i$-th candy, Timur consumes a quantity of sugar equal to $a_i$.
     22 
     23 Timur will ask you $q$ queries regarding his candies. For the $j$-th query you have to answer what is the minimum number of candies he needs to eat in order to reach a quantity of sugar greater than or equal to $x_j$ or print -1 if it's not possible to obtain such a quantity. In other words, you should print the minimum possible $k$ such that after eating $k$ candies, Timur consumes a quantity of sugar of at least $x_j$ or say that no possible $k$ exists.
     24 
     25 Note that he can't eat the same candy twice and queries are independent of each other (Timur can use the same candy in different queries).
     26 
     27 Input
     28 
     29 The first line of input contains a single integer $t$ ($1 \leq t \leq 1000$)  — the number of test cases. The description of test cases follows.
     30 
     31 The first line contains $2$ integers $n$ and $q$ ($1 \leq n, q \leq 1.5\cdot10^5$) — the number of candies Timur has and the number of queries you have to print an answer for respectively.
     32 
     33 The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \leq a_i \leq 10^4$) — the quantity of sugar in each of the candies respectively.
     34 
     35 Then $q$ lines follow.
     36 
     37 Each of the next $q$ lines contains a single integer $x_j$ ($1 \leq x_j \leq 2 \cdot 10^9$) – the quantity Timur wants to reach for the given query.
     38 
     39 It is guaranteed that the sum of $n$ and the sum of $q$ over all test cases do not exceed $1.5 \cdot 10^5$.
     40 
     41 Output
     42 
     43 For each test case output $q$ lines. For the $j$-th line output the number of candies Timur needs to eat in order to reach a quantity of sugar greater than or equal to $x_j$ or print -1 if it's not possible to obtain such a quantity.
     44 
     45 Example
     46 
     47 Input
     48 
     49 ```
     50 3
     51 
     52 8 7
     53 
     54 4 3 3 1 1 4 5 9
     55 
     56 1
     57 
     58 10
     59 
     60 50
     61 
     62 14
     63 
     64 15
     65 
     66 22
     67 
     68 30
     69 
     70 4 1
     71 
     72 1 2 3 4
     73 
     74 3
     75 
     76 1 2
     77 
     78 5
     79 
     80 4
     81 
     82 6
     83 ```
     84 
     85 Output
     86 
     87 ```
     88 1
     89 2
     90 -1
     91 2
     92 3
     93 4
     94 8
     95 1
     96 1
     97 -1
     98 ```
     99 
    100 Note
    101 
    102 For the first test case:
    103 
    104 For the first query, Timur can eat any candy, and he will reach the desired quantity.
    105 
    106 For the second query, Timur can reach a quantity of at least $10$ by eating the $7$-th and the $8$-th candies, thus consuming a quantity of sugar equal to $14$.
    107 
    108 For the third query, there is no possible answer.
    109 
    110 For the fourth query, Timur can reach a quantity of at least $14$ by eating the $7$-th and the $8$-th candies, thus consuming a quantity of sugar equal to $14$.
    111 
    112 For the second test case:
    113 
    114 For the only query of the second test case, we can choose the third candy from which Timur receives exactly $3$ sugar. It's also possible to obtain the same answer by choosing the fourth candy.