-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 ≤ 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: Подробная шпаргалка
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 хороши для повседневной разработки, но совершенно недостаточны для высоконагруженных систем. Представьте, что вы запускаете финансовую платформу, обрабатывающую. . .
|