-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 ≤ 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
|
16.09.2017, 12:37 | |
Ответы с готовыми решениями:
3
Понять смысл задачи - Описать функцию PowerA(x,a,eps) вещественного типа Не могу понять смысл задачи Не могу понять смысл поставленной задачи |
3565 / 2506 / 1174
Регистрация: 14.08.2016
Сообщений: 8,216
|
|
16.09.2017, 12:49 | 2 |
набора сразу нет т.к. он формируется по ходу дела, и на каждой операции добавления или удаления элемента надо высчитывать наименьшее отсутствующее
0
|
![]() 93 / 77 / 31
Регистрация: 29.08.2017
Сообщений: 188
|
||||||
16.09.2017, 13:47 | 3 | |||||
![]() Решение
Первое, что в голову пришло. Наверняка существуют намного более эффективные алгоритмы, раз уж это такая востребованная задача. У меня была еще одна идея, как это реализовать, но она сработала бы, если бы в наборе все числа были бы уникальны. Надо подумать/погуглить...
1
|
-22 / 2 / 0
Регистрация: 16.09.2015
Сообщений: 86
|
|
16.09.2017, 15:54 [ТС] | 4 |
LazySlacker, спасибо
1
|
16.09.2017, 15:54 | ||||||
Помогаю со студенческими работами здесь
4
Не могу понять понять смысл резидентной программы Помогите понять смысл задачи. Понять смысл задачи (решение квадратного уравнения) Не могу понять смысл задания Искать еще темы с ответами Или воспользуйтесь поиском по форуму:
|
|
Новые блоги и статьи
![]() |
||||
Чеклист для 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, нюансов конфигурирования, подходов к оптимизации и построению сложных. . .
|