Не могу понять смысл задачи "MEX"

@CBBBBB · Регистрация: 16.09.2015

Author24 — интернет-сервис помощи студентам

Помогите понять смысл задачи "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 ≤ 10⁹).
- 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) является одной из основных операций в теории игр.

Добавлено через 7 минут
Разобрался только что, кто сможет реализовать, каким методом воспользоваться?

@Diamante · 16.09.2017, 12:49

набора сразу нет т.к. он формируется по ходу дела, и на каждой операции добавления или удаления элемента надо высчитывать наименьшее отсутствующее

@LazySlacker · 16.09.2017, 13:47

Первое, что в голову пришло. Наверняка существуют намного более эффективные алгоритмы, раз уж это такая востребованная задача. У меня была еще одна идея, как это реализовать, но она сработала бы, если бы в наборе все числа были бы уникальны. Надо подумать/погуглить...

C#    
        
            
                
                
                
                
            
        
    Скопировано
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
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));
    }
}

@CBBBBB · 16.09.2017, 15:54 **[ТС]**

LazySlacker, спасибо

Новые блоги и статьи Все статьи Все блоги /
Чеклист для Kubernetes в продакшене: Лучшие практики для SRE Mr. Docker 19.03.2025 Когда сталкиваешься с запуском Kubernetes в продакшене, невольно задаешься вопросом: почему то, что так гладко работало в тестовой среде, вдруг начинает вызывать головную боль на боевых системах?. . .	Разработка продвинутого ИИ в Unity с использованием Behavior Graph GameUnited 19.03.2025 В разработке игр искусственный интеллект персонажей часто становится тем элементом, который превращает хорошую игру в выдающуюся. До недавнего времени разработчикам под Unity приходилось либо писать. . .	Словари в Python: методы работы, оптимизация, сериализация py-thonny 19.03.2025 Каждый хотя бы раз сталкивался с необходимостью хранить связанные данные, где важна не только сама информация, но и их взаимосвязь. В дебрях Python словари — это тот универсальный инструмент, который. . .	Реализация паттерна CQRS с Event Sourcing в PHP Jason-Webb 19.03.2025 CQRS (Command Query Responsibility Segregation) — это архитектурный паттерн, который разделяет операции чтения и записи данных в приложении. Если вы столкнулись с ситуацией, когда ваше PHP-приложение. . .	std::span в C++: Подпредставления и срезы NullReferenced 18.03.2025 Если вы когда-нибудь работали с большими объемами данных в C++, то наверняка сталкивались с необходимостью манипулировать отдельными частями массивов или контейнеров. Традиционные подходы часто. . .
std::span в C++: Доступ к элементам и итерирование NullReferenced 18.03.2025 В C++ каждый разработчик сталкивается с проблемой эффективного управления последовательностями данных. Представьте: вы работаете с массивом, передаете его в функцию, а затем в другую, и каждый раз. . .	Утечки памяти в C# UnmanagedCoder 18.03.2025 Когда мы говорим о разработке приложений на C#, то часто успокаиваем себя мыслью, что сборщик мусора решит все наши проблемы с памятью. "Память управляется автоматически" — эта мантра прочно засела в. . .	std::span в C++: Введение в невладеющее представление NullReferenced 18.03.2025 С появлением стандарта C++20 у нас появился новый инструмент — std::span, который представляет собой невладеющее представление для работы с последовательностями данных. std::span — это легковесный. . .	Введение в Dapr для разработчиков .NET UnmanagedCoder 18.03.2025 Разработка распределенных систем никогда не была настолько востребованной и одновременно такой сложной. Если вы . NET разработчик, то наверняка сталкивались с необходимостью жонглировать обнаружением. . .	Собеседование по Spring Boot: продвинутые вопросы и ответы Javaican 18.03.2025 Собеседования на позиции старших разработчиков и архитекторов требуют глубокого понимания внутренних механизмов Spring Boot, нюансов конфигурирования, подходов к оптимизации и построению сложных. . .

@CBBBBB -22 / 2 / 0 Регистрация: 16.09.2015 Сообщений: 86
		1
	Не могу понять смысл задачи "MEX" 16.09.2017, 12:37. Показов 2099. Ответов 3 Метки нет (Все метки) Помогите понять смысл задачи "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 ≤ 10⁹). - 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) является одной из основных операций в теории игр. Добавлено через 7 минут Разобрался только что, кто сможет реализовать, каким методом воспользоваться? 0

@Diamante 3565 / 2506 / 1174 Регистрация: 14.08.2016 Сообщений: 8,216
	16.09.2017, 12:49	2
	набора сразу нет т.к. он формируется по ходу дела, и на каждой операции добавления или удаления элемента надо высчитывать наименьшее отсутствующее 0

@CBBBBB -22 / 2 / 0 Регистрация: 16.09.2015 Сообщений: 86
	16.09.2017, 15:54 [ТС]	4
	LazySlacker, спасибо 1

Не могу понять смысл задачи "MEX"

Решение