Game with Multiset (Codeforces 1913C)
Tags: Greedy, bitmasks

In this problem, you are initially given an empty multiset. You have to process two types of queries:  ADD $$$x$$$ — add an element equal to $$$2^{x}$$$ to the multiset;  GET $$$w$$$ — say whether it is possible to take the sum of some subset of the current multiset and get a value equal to $$$w$$$. 

Input: The first line contains one integer $$$m$$$ ($$$1 \le m \le 10^5$$$) — the number of queries.Then $$$m$$$ lines follow, each of which contains two integers $$$t_i$$$, $$$v_i$$$, denoting the $$$i$$$-th query. If $$$t_i = 1$$$, then the $$$i$$$-th query is ADD $$$v_i$$$ ($$$0 \le v_i \le 29$$$). If $$$t_i = 2$$$, then the $$$i$$$-th query is GET $$$v_i$$$ ($$$0 \le v_i \le 10^9$$$).

Output: For each GET query, print YES if it is possible to choose a subset with sum equal to $$$w$$$, or NO if it is impossible.


Sample Inputs:
5
1 0
1 0
1 0
2 3
2 4

7
1 0
1 1
1 2
1 10
2 4
2 6
2 7

Sample Outputs:
YES
NO

YES
YES
YES

Solution (Python):
import sys

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

def solve():
    st = [0] * 30
    mi = [1 << i for i in range(30)]
    for _ in range(int(readline())):
        (ch, x) = map(int, readline().split())
        if ch == 1:
            st[x] += 1
        else:
            i = 29
            while x != 0 and i >= 0:
                t = st[i]
                m = mi[i]
                x = x - m * t if x // m >= t else x - x // m * m
                i -= 1
            if x == 0:
                print('YES')
            else:
                print('NO')
solve()

Solution (Python):
import sys

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

def qmi(k):
    a = 2
    res = 1
    while k > 0:
        if k & 1:
            res *= a
        a *= a
        k >>= 1
    return res

def solve():
    st = [0] * 30
    mi = [qmi(i) for i in range(30)]
    for _ in range(int(readline())):
        (ch, x) = map(int, readline().split())
        if ch == 1:
            st[x] += 1
        else:
            i = 29
            while x != 0 and i >= 0:
                t = st[i]
                m = mi[i]
                x = x - m * t if x // m >= t else x - x // m * m
                i -= 1
            if x == 0:
                print('YES')
            else:
                print('NO')
solve()

Solution (Python):
from sys import stdin, stdout
LOG = 30
cnt = [0] * LOG
ans = []

def solve(t, v):
    if t == 1:
        cnt[v] += 1
    else:
        nw = 0
        remainder = v
        for i in range(LOG):
            r = remainder & 1
            if r > nw + cnt[i]:
                ans.append('NO')
                return
            remainder >>= 1
            v -= r
            nw = (nw + cnt[i] - r) // 2
        ans.append('YES' if nw >= v >> 30 else 'NO')

def main():
    for _ in range(int(stdin.readline())):
        (t, v) = map(int, stdin.readline().split())
        solve(t, v)
    stdout.write('\n'.join(ans))
if __name__ == '__main__':
    main()