Не могу понять смысл задачи "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: Подробная шпаргалка Mr. Docker 15.03.2025 Kubernetes — это открытая платформа для автоматизации развертывания, масштабирования и управления контейнеризированными приложениями. Он был создан для решения проблем, с которыми сталкиваются. . .	Лучшие PHP REST API фреймворки Jason-Webb 15.03.2025 Современные PHP REST API фреймворки предлагают большой набор функциональности: от автоматической валидации данных и управления маршрутизацией до генерации документации и интеграции с различными. . .	Многопоточность в Java с Project Loom: виртуальные или обычные потоки Javaican 15.03.2025 Многопоточность всегда была одноим из основных элементов в разработке современного программного обеспечения. Она позволяет приложениям обрабатывать несколько задач одновременно, что критично для. . .	Что нового в Swift 6 и особенности миграции mobDevWorks 15.03.2025 Swift 6 — это новый крупный релиз языка программирования от Apple, анонсированный на WWDC 2024. Если вы следили за эволюцией Swift, то наверняка заметили, что многие значимые возможности, которые. . .	Вопросы на собеседовании по Android mobDevWorks 14.03.2025 По данным статистики, Android занимает более 70% мирового рынка мобильных операционных систем, что делает платформу привлекательной как для начинающих разработчиков, так и для опытных профессионалов. . . .
Лучшие игровые движки для Python py-thonny 14.03.2025 Python обеспечивает разработчиков игр мощными движками и фреймворками, которые позволяют воплотить практически любую идею — от простой аркады до визуального романа с разветвленным сюжетом. Главное. . .	Бессерверный JavaScript: Разработка масштабируемых API с AWS Lambda run.dev 14.03.2025 Но что такое бессерверные вычисления на самом деле? По сути, это модель облачных вычислений, где разработчик фокусируется исключительно на создании бизнес-логики, не тратя время на настройку. . .	Безопасность кода в C++26: Менеджеры ресурсов и висячие ссылки NullReferenced 14.03.2025 C++ всегда был языком, предоставляющим разработчикам большие возможности и гибкость, но вместе с тем требующим ответственности. Одной из самых коварных проблем даже для опытных программистов остаются. . .	smart-agent proper interface settings (2025) jigi33 14.03.2025 Smart-agent proper interface settings (mart 2025). (see screenshots to look at "Etalon" ARM)	Продвинутые настройки JVM Javaican 14.03.2025 Стандартные параметры запуска JVM хороши для повседневной разработки, но совершенно недостаточны для высоконагруженных систем. Представьте, что вы запускаете финансовую платформу, обрабатывающую. . .

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

Решение