codeforces-scrape

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

1913C.md (1122B)


      1 Source: https://codeforces.com/problemset/problem/1913/C
      2 
      3 C. Game with Multiset
      4 
      5 time limit per test
      6 
      7 1.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 In this problem, you are initially given an empty multiset. You have to process two types of queries:
     22 
     23 1. ADD $x$ — add an element equal to $2^{x}$ to the multiset;
     24 2. 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$.
     25 
     26 Input
     27 
     28 The first line contains one integer $m$ ($1 \le m \le 10^5$) — the number of queries.
     29 
     30 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$).
     31 
     32 Output
     33 
     34 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.
     35 
     36 Examples
     37 
     38 Input
     39 
     40 ```
     41 5
     42 
     43 1 0
     44 
     45 1 0
     46 
     47 1 0
     48 
     49 2 3
     50 
     51 2 4
     52 ```
     53 
     54 Output
     55 
     56 ```
     57 YES
     58 NO
     59 ```
     60 
     61 Input
     62 
     63 ```
     64 7
     65 
     66 1 0
     67 
     68 1 1
     69 
     70 1 2
     71 
     72 1 10
     73 
     74 2 4
     75 
     76 2 6
     77 
     78 2 7
     79 ```
     80 
     81 Output
     82 
     83 ```
     84 YES
     85 YES
     86 YES
     87 ```