codeforces-scrape

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

1732D1.md (2401B)


      1 Source: https://codeforces.com/problemset/problem/1732/D1
      2 
      3 D1. Balance (Easy version)
      4 
      5 time limit per test
      6 
      7 3 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 This is the easy version of the problem. The only difference is that in this version there are no "remove" queries.
     22 
     23 Initially you have a set containing one element — $0$. You need to handle $q$ queries of the following types:
     24 
     25 * + $x$ — add the integer $x$ to the set. It is guaranteed that this integer is not contained in the set;
     26 * ? $k$ — find the $k\text{-mex}$ of the set.
     27 
     28 In our problem, we define the $k\text{-mex}$ of a set of integers as the smallest non-negative integer $x$ that is divisible by $k$ and which is not contained in the set.
     29 
     30 Input
     31 
     32 The first line contains an integer $q$ ($1 \leq q \leq 2 \cdot 10^5$) — the number of queries.
     33 
     34 The following $q$ lines describe the queries.
     35 
     36 An addition query of integer $x$ is given in the format + $x$ ($1 \leq x \leq 10^{18}$). It is guaranteed that $x$ was not contained in the set.
     37 
     38 A search query of $k\text{-mex}$ is given in the format ? $k$ ($1 \leq k \leq 10^{18}$).
     39 
     40 It is guaranteed that there will be at least one query of type ?.
     41 
     42 Output
     43 
     44 For each query of type ? output a single integer — the $k\text{-mex}$ of the set.
     45 
     46 Examples
     47 
     48 Input
     49 
     50 ```
     51 15
     52 
     53 + 1
     54 
     55 + 2
     56 
     57 ? 1
     58 
     59 + 4
     60 
     61 ? 2
     62 
     63 + 6
     64 
     65 ? 3
     66 
     67 + 7
     68 
     69 + 8
     70 
     71 ? 1
     72 
     73 ? 2
     74 
     75 + 5
     76 
     77 ? 1
     78 
     79 + 1000000000000000000
     80 
     81 ? 1000000000000000000
     82 ```
     83 
     84 Output
     85 
     86 ```
     87 3
     88 6
     89 3
     90 3
     91 10
     92 3
     93 2000000000000000000
     94 ```
     95 
     96 Input
     97 
     98 ```
     99 6
    100 
    101 + 100
    102 
    103 ? 100
    104 
    105 + 200
    106 
    107 ? 100
    108 
    109 + 50
    110 
    111 ? 50
    112 ```
    113 
    114 Output
    115 
    116 ```
    117 200
    118 300
    119 150
    120 ```
    121 
    122 Note
    123 
    124 In the first example:
    125 
    126 After the first and second queries, the set will contain elements $\{0, 1, 2\}$. The smallest non-negative number that is divisible by $1$ and is not contained in the set is $3$.
    127 
    128 After the fourth query, the set will contain the elements $\{0, 1, 2, 4\}$. The smallest non-negative number that is divisible by $2$ and is not contained in the set is $6$.
    129 
    130 In the second example:
    131 
    132 * Initially, the set contains only the element $\{0\}$.
    133 * After adding an integer $100$ the set contains elements $\{0, 100\}$.
    134 * $100\text{-mex}$ of the set is $200$.
    135 * After adding an integer $200$ the set contains elements $\{0, 100, 200\}$.
    136 * $100\text{-mex}$ of the set is $300$.
    137 * After adding an integer $50$ the set contains elements $\{0, 50, 100, 200\}$.
    138 * $50\text{-mex}$ of the set is $150$.