Algorithm

D. Coins and Queries
time limit per test
2 seconds
memory limit per test
256 megabytes
Problem link- https://codeforces.com/contest/1003/problem/D
input
standard input
output
standard output

Polycarp has n� coins, the value of the i�-th coin is ai��. It is guaranteed that all the values are integer powers of 22 (i.e. ai=2d��=2� for some non-negative integer number d�).

Polycarp wants to know answers on q� queries. The j�-th query is described as integer number bj��. The answer to the query is the minimum number of coins that is necessary to obtain the value bj�� using some subset of coins (Polycarp can use only coins he has). If Polycarp can't obtain the value bj��, the answer to the j�-th query is -1.

The queries are independent (the answer on the query doesn't affect Polycarp's coins).

Input

The first line of the input contains two integers n� and q� (1≤n,q≤2⋅1051≤�,�≤2⋅105) — the number of coins and the number of queries.

The second line of the input contains n� integers a1,a2,…,an�1,�2,…,�� — values of coins (1≤ai≤2⋅1091≤��≤2⋅109). It is guaranteed that all ai�� are integer powers of 22 (i.e. ai=2d��=2� for some non-negative integer number d�).

The next q� lines contain one integer each. The j�-th line contains one integer bj�� — the value of the j�-th query (1≤bj≤1091≤��≤109).

Output

Print q� integers ansj����. The j�-th integer must be equal to the answer on the j�-th query. If Polycarp can't obtain the value bj�� the answer to the j�-th query is -1.

Example
input
Copy
5 4
2 4 8 2 4
8
5
14
10
output
Copy
1
-1
3
2

 



 

Code Examples

#1 Code Example with C++ Programming

Code - C++ Programming

#include <bits/stdc++.h>

using namespace std;

int const N = 2e5 + 1;
int n, q, a[N], fr[35], fr1[35];

bool check() {
  for(int i = 0; i < 35; ++i)
    if(fr1[i] != 0)
      return false;
  return true;
}

int main() {
  scanf("%d %d", &n, &q);
  for(int i = 0; i < n; ++i) {
    scanf("%d", a + i);
    bitset<32> bs(a[i]);
    for(int i = 0; i < 32; ++i)
      if(bs[i] == 1)
        ++fr[i];
  }

  while(q-- != 0) {
    int tmp;
    scanf("%d", &tmp>;
    bitset<32> bs(tmp);

    memset(fr1, 0, sizeof fr1);
    for(int i = 0; i < 32; ++i)
      fr1[i] = bs[i];
    
    int cnt = 0;
    for(int i = 31; i >= 0; --i) {
      if(i > 0 && fr1[i] != 0 && fr[i] == 0) {
        fr1[i - 1] += fr1[i] * 2;
        fr1[i] = 0;
      } else if(i > 0 && fr1[i] != 0 && fr[i] < fr1[i]) {
        fr1[i - 1] += (fr1[i] - fr[i]) * 2;
        cnt += fr[i];
        fr1[i] = 0;
      } else if(fr1[i] != 0 && fr[i] >= fr1[i]) {
        cnt += fr1[i];
        fr1[i] = 0;
      }
    }

    if(check())
      printf("%d\n", cnt);
    else
      puts("-1");
  }

  return 0;
}
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
5 4
2 4 8 2 4
8
5
14
10

Output

x
–
+
cmd
1
-1
3
2
Advertisements

Demonstration

Codeforces Solution-D. Coins and Queries-Solution in C, C++, Java, Python,Coins and Queries

Previous
Codeforces solution 1080-B-B. Margarite and the best present codeforces solution
Next
CodeChef solution DETSCORE - Determine the Score CodeChef solution C,C+