Не могу понять смысл задачи "MEX" - C#
Формулировка задачи:
Помогите понять смысл задачи "MEX". Почему набор не задается во входных данных?
Условие задачи:
Примеры:
Примечание:
Задача «MEX»
ограничение по времени на тест3 секунды ограничение по памяти на тест256 мегабайт вводstdin выводstdout Операция MEX для набора целых неотрицательных чисел возвращает наименьшее неотрицательное целое число, не содержащееся в наборе. Например, для набора (0, 1, 2, 2, 4, 4, 11) это значение равно 3, для набора (1, 1, 2, 5, 7) это значение равно 0, а для набора (0, 1, 2, 2, 2, 3) это значение равно 4. В наборе могут встречаться одинаковые числа. Вам задана последовательность из нескольких операций одного из двух видов: + x — добавить число x в набор. - x — удалить одно вхождение числа x из набора (если числа x в наборе нет, то операция игнорируется). Изначально набор пуст. Вам необходимо вывести значение MEX для набора после применения каждой из операций. Операции выполняются последовательно одна за другой.Входные данные
В первой строке содержится число n — количество операций (1 ≤ n ≤ 150000). В следующих n строках содержатся операции, по одной в строке. Операция может быть одного из двух видов: + x — добавить число x в набор (0 ≤ x ≤ 109). - x — удалить одно вхождение числа x из набора. Знак операции и число разделены единичным пробелом.Выходные данные
Выведите n чисел через пробел — значение MEX для набора после применения каждой из указанных операций.входные данные
7 + 2 + 1 + 0 + 4 + 2 - 2 - 2выходные данные
0 0 3 3 3 3 2входные данные
6 + 0 + 1 + 0 - 1 - 0 - 0выходные данные
1 2 2 1 1 0
Операция MEX (minimum excludant) является одной из основных операций в теории игр.
Разобрался только что, кто сможет реализовать, каким методом воспользоваться?
Решение задачи: «Не могу понять смысл задачи "MEX"»
textual
Листинг программы
using System;
using System.Collections.Generic;
class Program
{
public static void Main()
{
List<int> mex = new List<int>();
Dictionary<int, int> bag = new Dictionary<int, int>();
for (int i = Int32.Parse(Console.ReadLine()); i > 0; --i)
{
string[] s = Console.ReadLine().Split();
int x = Int32.Parse(s[1]);
int n;
if (!bag.TryGetValue(x, out n)) n = 0;
n += s[0] == "+" ? 1 : -1;
if (n > 0)
{
bag[x] = n;
}
else if (n == 0)
{
bag.Remove(x);
}
x = 0;
while (bag.ContainsKey(x)) ++x;
mex.Add(x);
}
Console.WriteLine(String.Join(" ", mex));
}
}