Не могу понять смысл задачи "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, спасибо

Новые блоги и статьи Все статьи Все блоги /
Циклы for в Python py-thonny 17.03.2025 Существует множество ситуаций, когда нам нужно выполнить одно и то же действие несколько раз. Цикл for в Python — настоящий рабочий конь для большинства программистов. Если вам нужно пройтись по всем. . .	Предсказание ветвлений - путь к высокопроизводительному C++ NullReferenced 17.03.2025 В высокопроизводительном программировании на C++ каждый такт процессора на счету. Когда речь заходит о разработке систем с низкой задержкой — будь то высокочастотная торговля, обработка потоковых. . .	Паттерн CQRS в C# UnmanagedCoder 17.03.2025 Создание сложных корпоративных приложений часто требует нестандартных подходов к архитектуре. Один из таких подходов — паттерн CQRS (Command Query Responsibility Segregation), предлагающий простую,. . .	Паттерн Цепочка ответственности в C# UnmanagedCoder 17.03.2025 Цепочка ответственности — это поведенческий паттерн проектирования, который позволяет передавать запросы последовательно по цепочке потенциальных обработчиков, пока один из них не обработает запрос. . . .	Создаем микросервисы с NestJS, TCP и Typescript run.dev 17.03.2025 NestJS — фреймворк, который значительно упрощает создание серверных приложений на Node. js. Его прелесть в том, что он комбинирует концепции ООП, функционального программирования и предлагает. . .
Гексагональная архитектура со Spring Boot Javaican 17.03.2025 Если вы когда-нибудь сталкивались с ситуацией, когда внесение простых изменений в базу данных или пользовательский интерфейс заставляло вас переписывать весь код, то вы точно оцените элегантность. . .	Позиционирование Kafka Consumer и Seek-операции Javaican 17.03.2025 Что же такое Consumer Seek в Kafka? По сути, это API-метод, который позволяет программно указать, с какой позиции (offset) Consumer должен начать или продолжить чтение данных из партиции. Без этого. . .	Python NumPy: Лучшие практики и примеры py-thonny 17.03.2025 NumPy (Numerical Python) — одна из ключевых библиотек для научных вычислений в Python. Она превращает Python из просто удобного языка общего назначения в среду для проведения сложных математических. . .	Java Micronaut в Docker: контейнеризация с Maven и Jib Javaican 16.03.2025 Когда речь заходит о микросервисной архитектуре на Java, фреймворк Micronaut выделяется среди конкурентов. Он создан с учётом особенностей облачных сред и контейнеров, что делает его идеальным. . .	Управление зависимостями в Java: Сравнение Spring, Guice и Dagger 2 Javaican 16.03.2025 Инъекция зависимостей (Dependency Injection, DI) — один из фундаментальных паттернов проектирования, который радикально меняет подход к созданию гибких и тестируемых Java-приложений. Суть этого. . .

@CBBBBB -22 / 2 / 0 Регистрация: 16.09.2015 Сообщений: 86
		1
	Не могу понять смысл задачи "MEX" 16.09.2017, 12:37. Показов 2093. Ответов 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"

Решение