A. Mahmoud and Ehab and the MEX

Codeforces
IDCF862A
Time2000ms
Memory256MB
Difficulty
greedyimplementation
English · Original
Chinese · Translation
Formal · Original
Dr. Evil kidnapped Mahmoud and Ehab in the evil land because of their performance in the Evil Olympiad in Informatics (EOI). He decided to give them some problems to let them go. Dr. Evil is interested in sets, He has a set of _n_ integers. Dr. Evil calls a set of integers _evil_ if the _MEX_ of it is exactly _x_. the _MEX_ of a set of integers is the minimum non-negative integer that doesn't exist in it. For example, the _MEX_ of the set {0, 2, 4} is 1 and the _MEX_ of the set {1, 2, 3} is 0 . Dr. Evil is going to make his set _evil_. To do this he can perform some operations. During each operation he can add some non-negative integer to his set or erase some element from it. What is the minimal number of operations Dr. Evil has to perform to make his set _evil_? ## Input The first line contains two integers _n_ and _x_ (1 ≤ _n_ ≤ 100, 0 ≤ _x_ ≤ 100) — the size of the set Dr. Evil owns, and the desired _MEX_. The second line contains _n_ distinct non-negative integers not exceeding 100 that represent the set. ## Output The only line should contain one integer — the minimal number of operations Dr. Evil should perform. [samples] ## Note For the first test case Dr. Evil should add 1 and 2 to the set performing 2 operations. For the second test case Dr. Evil should erase 0 from the set. After that, the set becomes empty, so the _MEX_ of it is 0. In the third test case the set is already _evil_.
Dr. Evil 因为 Mahmoud 和 Ehab 在 Evil 竞赛信息学(EOI)中的表现,将他们绑架到了邪恶之地。他决定给他们一些问题,以便放他们走。 Dr. Evil 对集合感兴趣,他有一个包含 #cf_span[n] 个整数的集合。Dr. Evil 称一个整数集合为 _evil_ 的,当且仅当它的 _MEX_ 恰好为 #cf_span[x]。一个整数集合的 _MEX_ 是指不在该集合中的最小非负整数。例如,集合 #cf_span[{0, 2, 4}] 的 _MEX_ 是 #cf_span[1],集合 #cf_span[{1, 2, 3}] 的 _MEX_ 是 #cf_span[0]。 Dr. Evil 想要将他的集合变为 _evil_。为此,他可以执行一些操作。每次操作中,他可以向集合中添加某个非负整数,或者从集合中删除某个元素。请问 Dr. Evil 至少需要执行多少次操作才能使他的集合成为 _evil_? 第一行包含两个整数 #cf_span[n] 和 #cf_span[x](#cf_span[1 ≤ n ≤ 100],#cf_span[0 ≤ x ≤ 100])——分别表示 Dr. Evil 拥有的集合的大小和目标 _MEX_。 第二行包含 #cf_span[n] 个互不相同的非负整数(均不超过 #cf_span[100]),表示该集合。 仅输出一行,包含一个整数——Dr. Evil 所需的最少操作次数。 对于第一个测试用例,Dr. Evil 应该向集合中添加 #cf_span[1] 和 #cf_span[2],共执行 #cf_span[2] 次操作。 对于第二个测试用例,Dr. Evil 应该从集合中删除 #cf_span[0]。删除后,集合变为空集,其 _MEX_ 为 #cf_span[0]。 在第三个测试用例中,集合已经是 _evil_ 的。 ## Input 第一行包含两个整数 #cf_span[n] 和 #cf_span[x](#cf_span[1 ≤ n ≤ 100],#cf_span[0 ≤ x ≤ 100])——分别表示 Dr. Evil 拥有的集合的大小和目标 _MEX_。第二行包含 #cf_span[n] 个互不相同的非负整数(均不超过 #cf_span[100]),表示该集合。 ## Output 仅输出一行,包含一个整数——Dr. Evil 所需的最少操作次数。 [samples] ## Note 对于第一个测试用例,Dr. Evil 应该向集合中添加 #cf_span[1] 和 #cf_span[2],共执行 #cf_span[2] 次操作。 对于第二个测试用例,Dr. Evil 应该从集合中删除 #cf_span[0]。删除后,集合变为空集,其 _MEX_ 为 #cf_span[0]。 在第三个测试用例中,集合已经是 _evil_ 的。
**Definitions** Let $ n, x \in \mathbb{Z} $ with $ 1 \leq n \leq 100 $, $ 0 \leq x \leq 100 $. Let $ S \subseteq \mathbb{Z}_{\geq 0} $ be a finite set with $ |S| = n $ and $ \max(S) \leq 100 $. **Constraints** All elements of $ S $ are distinct and lie in $ \{0, 1, \dots, 100\} $. **Objective** Find the minimum number of operations (additions or deletions) to transform $ S $ into a set $ S' $ such that $ \mathrm{MEX}(S') = x $, where $$ \mathrm{MEX}(S') = \min \left( \mathbb{Z}_{\geq 0} \setminus S' \right). $$ **Condition for MEX = x** $ \mathrm{MEX}(S') = x $ if and only if: - $ \{0, 1, \dots, x-1\} \subseteq S' $, and - $ x \notin S' $. **Minimal Operations** Let: - $ A = \{0, 1, \dots, x-1\} \setminus S $: elements missing from $ S $ that must be added. - $ B = S \cap \{0, 1, \dots, x-1\} $: elements in $ S $ that are correct (already present). - $ C = S \setminus \{x\} $: elements in $ S $ not equal to $ x $. - $ D = \{x\} \cap S $: whether $ x $ is present (1 if yes, 0 if no). Then: - Number of **additions** needed: $ |A| = x - |B| $. - Number of **deletions** needed: $ D $ (i.e., 1 if $ x \in S $, else 0). Thus, minimal operations: $$ |x - |S \cap \{0, 1, \dots, x-1\}|| + \mathbb{I}_{x \in S} $$
Samples
Input #1
5 3
0 4 5 6 7
Output #1
2
Input #2
1 0
0
Output #2
1
Input #3
5 0
1 2 3 4 5
Output #3
0
API Response (JSON)
{
  "problem": {
    "name": "A. Mahmoud and Ehab and the MEX",
    "description": {
      "content": "Dr. Evil kidnapped Mahmoud and Ehab in the evil land because of their performance in the Evil Olympiad in Informatics (EOI). He decided to give them some problems to let them go. Dr. Evil is interest",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF862A"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Dr. Evil kidnapped Mahmoud and Ehab in the evil land because of their performance in the Evil Olympiad in Informatics (EOI). He decided to give them some problems to let them go.\n\nDr. Evil is interest...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "Dr. Evil 因为 Mahmoud 和 Ehab 在 Evil 竞赛信息学(EOI)中的表现,将他们绑架到了邪恶之地。他决定给他们一些问题,以便放他们走。\n\nDr. Evil 对集合感兴趣,他有一个包含 #cf_span[n] 个整数的集合。Dr. Evil 称一个整数集合为 _evil_ 的,当且仅当它的 _MEX_ 恰好为 #cf_span[x]。一个整数集合的 _MEX_ 是指不在该集合...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n, x \\in \\mathbb{Z} $ with $ 1 \\leq n \\leq 100 $, $ 0 \\leq x \\leq 100 $.  \nLet $ S \\subseteq \\mathbb{Z}_{\\geq 0} $ be a finite set with $ |S| = n $ and $ \\max(S) \\leq 100 $.\n\n*...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}
Full JSON Raw Segments