Coins and Queries (Codeforces 1003D)
Tags: Greedy, greedy

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$$$).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.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 \le n, q \le 2 \cdot 10^5$$$) — the number of coins and the number of queries.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$$$).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$$$).

Output: 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.


Sample Inputs:
5 4
2 4 8 2 4
8
5
14
10

Sample Outputs:
1
-1
3
2

Solution (Python):
import sys, os, io
from sys import stdin
from math import log, gcd, ceil
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from bisect import bisect_left, bisect_right
import math

def ii():
    return int(input())

def li():
    return list(map(int, input().split()))
if os.path.exists('input.txt'):
    sys.stdin = open('input.txt', 'r')
    sys.stdout = open('output.txt', 'w')
else:
    input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
no = 'NO'
yes = 'YES'

def solve():
    (n, q) = li()
    a = li()
    d = defaultdict(lambda : 0)
    for i in a:
        d[i] += 1
    k = list(d.keys())
    k.sort()
    k.reverse()
    for i in range(q):
        b = ii()
        cnt = 0
        f = 0
        for j in k:
            cnt += min(d[j], b // j)
            b = b - j * min(d[j], b // j)
        if b != 0:
            cnt = -1
        print(cnt)
t = 1
for _ in range(t):
    solve()

Solution (Python):
import os
import sys
from collections import *
from bisect import *
from io import BytesIO, IOBase

def vsInput():
    sys.stdin = open('input.txt', 'r')
    sys.stdout = open('output.txt', 'w')
BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
ALPHA = 'abcdefghijklmnopqrstuvwxyz'
M = 998244353
EPS = 1e-06

def Ceil(a, b):
    return a // b + int(a % b > 0)

def value():
    return tuple(map(int, input().split()))

def array():
    return [int(i) for i in input().split()]

def Int():
    return int(input())

def Str():
    return input()

def arrayS():
    return [i for i in input().split()]
(n, q) = value()
a = Counter(array())
keys = sorted(a.keys(), reverse=True)
for _ in range(q):
    x = Int()
    ans = 0
    for k in keys:
        need = min(x // k, a[k])
        ans += need
        x -= need * k
    if x:
        ans = -1
    print(ans)

Solution (Python):
from sys import stdout, stdin, setrecursionlimit
from io import BytesIO, IOBase
from collections import *
from itertools import *
from random import *
from bisect import *
from string import *
from queue import *
from heapq import *
from math import *
from re import *
from os import *

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = read(self._fd, max(fstat(self._fd).st_size, 8192))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = read(self._fd, max(fstat(self._fd).st_size, 8192))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
(stdin, stdout) = (IOWrapper(stdin), IOWrapper(stdout))

def fast():
    return stdin.readline().strip()

def zzz():
    return [int(i) for i in fast().split()]
(z, zz) = (fast, lambda : map(int, z().split()))
(szz, graph, mod, szzz) = (lambda : sorted(zz()), {}, 10 ** 9 + 7, lambda : sorted(zzz()))

def lcd(xnum1, xnum2):
    return xnum1 * xnum2 // gcd(xnum1, xnum2)

def output(answer, end='\n'):
    stdout.write(str(answer) + end)
dx = [-1, 1, 0, 0, 1, -1, 1, -1]
dy = [0, 0, 1, -1, 1, -1, -1, 1]
''
(n, k) = zzz()
arr = zzz()
lst = [0] * 31
for i in arr:
    lst[int(log2(i))] += 1
for i in range(k):
    x = int(z())
    ans = 0
    for j in range(30, -1, -1):
        cnt = min(x >> j, lst[j])
        ans += cnt
        x -= cnt << j
    if x == 0:
        output(ans)
    else:
        output(-1)