Форум программистов, компьютерный форум, киберфорум
C# для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 5.00/11: Рейтинг темы: голосов - 11, средняя оценка - 5.00
-22 / 2 / 0
Регистрация: 16.09.2015
Сообщений: 86
1

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

16.09.2017, 12:37. Показов 2085. Ответов 3
Метки нет (Все метки)

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


Добавлено через 7 минут
Разобрался только что, кто сможет реализовать, каким методом воспользоваться?
0
Лучшие ответы (1)
Programming
Эксперт
39485 / 9562 / 3019
Регистрация: 12.04.2006
Сообщений: 41,671
Блог
16.09.2017, 12:37
Ответы с готовыми решениями:

Понять смысл задачи - Описать функцию PowerA(x,a,eps) вещественного типа
Описать функцию PowerA(x,a,eps) вещественного типа (параметры x, a, eps — вещественные, |x| < 1, a > 0, eps> 0), находящую...

Не могу понять смысл задачи
Create static method search(String data, String key), which returns amount of String key in data array. In main method, call search method....

Не могу понять смысл поставленной задачи
Вводится текст-набор символов, конец - ".". Программа должна разбить его на слова (последовательности букв латинское алфавита, все другое -...

3
3565 / 2506 / 1174
Регистрация: 14.08.2016
Сообщений: 8,216
16.09.2017, 12:49 2
набора сразу нет т.к. он формируется по ходу дела, и на каждой операции добавления или удаления элемента надо высчитывать наименьшее отсутствующее
0
 Аватар для LazySlacker
93 / 77 / 31
Регистрация: 29.08.2017
Сообщений: 188
16.09.2017, 13:47 3
Лучший ответ Сообщение было отмечено CBBBBB как решение

Решение

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

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));
    }
}
1
-22 / 2 / 0
Регистрация: 16.09.2015
Сообщений: 86
16.09.2017, 15:54  [ТС] 4
LazySlacker, спасибо
1
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
inter-admin
Эксперт
29715 / 6470 / 2152
Регистрация: 06.03.2009
Сообщений: 28,500
Блог
16.09.2017, 15:54
Помогаю со студенческими работами здесь

Не могу понять математический смысл условия задачи
1. Выяснить, какими из свойств: рефлексивность, антирефлексивность, симметричность, антисимметричность, транзитивность, связность...

Не могу понять понять смысл резидентной программы
Суть препод кинул резидент, сказал чтобы сами разбирались. Увидел что ее выкладывали уже, но в ветке этой темы, там тоже не объяснили, как...

Помогите понять смысл задачи.
Технология клиент-сервер на основе сокетов Windows. Реализация сокетов через классы протокол TCP. Аутентификация пользователей по паролям....

Понять смысл задачи (решение квадратного уравнения)
Using the 3 methods above, create an application that calculates the roots of an equation of second degree: ax ² + bx + c = 0 For it...

Не могу понять смысл задания
Определить тип заданных выражений и найти их значения. Составить систему тестов и вычислить полученное выражение для нескольких значений n...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
4
Ответ Создать тему

Редактор формул (кликните на картинку в правом углу, чтобы закрыть)
Новые блоги и статьи
Осваиваем 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 хороши для повседневной разработки, но совершенно недостаточны для высоконагруженных систем. Представьте, что вы запускаете финансовую платформу, обрабатывающую. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2025, CyberForum.ru
Выделить код Копировать код Сохранить код Нормальный размер Увеличенный размер