codeforces-scrape

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

2021B.md (2305B)


      1 Source: https://codeforces.com/problemset/problem/2021/B
      2 
      3 B. Maximize Mex
      4 
      5 time limit per test
      6 
      7 1 second
      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 You are given an array $a$ of $n$ positive integers and an integer $x$. You can do the following two-step operation any (possibly zero) number of times:
     22 
     23 1. Choose an index $i$ ($1 \leq i \leq n$).
     24 2. Increase $a_i$ by $x$, in other words $a_i := a_i + x$.
     25 
     26 Find the maximum value of the $\operatorname{MEX}$ of $a$ if you perform the operations optimally.
     27 
     28 The $\operatorname{MEX}$ (minimum excluded value) of an array is the smallest non-negative integer that is not in the array. For example:
     29 
     30 * The $\operatorname{MEX}$ of $[2,2,1]$ is $0$ because $0$ is not in the array.
     31 * The $\operatorname{MEX}$ of $[3,1,0,1]$ is $2$ because $0$ and $1$ are in the array but $2$ is not.
     32 * The $\operatorname{MEX}$ of $[0,3,1,2]$ is $4$ because $0$, $1$, $2$ and $3$ are in the array but $4$ is not.
     33 
     34 Input
     35 
     36 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 5000$). The description of the test cases follows.
     37 
     38 The first line of each test case contains two integers $n$ and $x$ ($1 \le n \le 2 \cdot 10^5$; $1 \le x \le 10^9$) — the length of the array and the integer to be used in the operation.
     39 
     40 The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \le a_i \le 10^9$) — the given array.
     41 
     42 It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.
     43 
     44 Output
     45 
     46 For each test case, output a single integer: the maximum $\operatorname{MEX}$ of $a$ if you perform the operations optimally.
     47 
     48 Example
     49 
     50 Input
     51 
     52 ```
     53 3
     54 
     55 6 3
     56 
     57 0 3 2 1 5 2
     58 
     59 6 2
     60 
     61 1 3 4 1 0 2
     62 
     63 4 5
     64 
     65 2 5 10 3
     66 ```
     67 
     68 Output
     69 
     70 ```
     71 4
     72 6
     73 0
     74 ```
     75 
     76 Note
     77 
     78 In the first test case, the $\operatorname{MEX}$ of $a$ is $4$ without performing any operations, which is the maximum.
     79 
     80 In the second test case, the $\operatorname{MEX}$ of $a$ is $5$ without performing any operations. If we perform two operations both with $i=1$, we will have the array $a=[5,3,4,1,0,2]$. Then, the $\operatorname{MEX}$ of $a$ will become $6$, which is the maximum.
     81 
     82 In the third test case, the $\operatorname{MEX}$ of $a$ is $0$ without performing any operations, which is the maximum.