11/04/2025 01:10:33

Рабочее место участника

Выбрать соревнование

Задачи

Послать решение

Результаты проверки

Статистика по задачам

Вопросы и ответы

Результаты соревнования

Задачи

2688. Перестановка

Ограничения: время – 200ms/500ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (15)

Дана последовательность из $N$ натуральных чисел. Разрешается выполнять одно из двух действий

удалить одно число из последовательности;
добавить в эту последовательность произвольное новое число.

Требуется за наименьшее количество действий превратить эту последовательность в перестановку. Перестановкой называется непустая последовательность из $M$ ( $M>=1$ ) чисел от 1 до $M$ , в которой каждое число встречается ровно один раз. Обратите внимание, что порядок чисел в перестановке не важен. Например, из последовательности {2,1,4,1,100} нужно удалить числа 1 и 100 и добавить число 3, чтобы получилась перестановка {2,1,4,3}. Другим вариантом с 3 действиями является удаление чисел 1,100 и 3, чтобы получилась перестановка {2,1}. Получение других перестановок (например, {1} или {2,1,4,3,5}) потребует 4 или более действий, что больше минимума в 3 действия.

Первая строка ввода содержит одно целое число $N$ ( $1 <= N <= 10^5$ ) – количество чисел в исходной последовательности, вторая строка ввода содержит $N$ целых чисел в диапазоне от 1 до $10^9$ включительно — исходная последовательность чисел.

В первой строке вывести одно целое число $K$ — минимальное количество действий для превращения последовательности в перестановку. В следующих $K$ строках вывести сами действия, каждое действие на отдельной строке. Если число $X$ нужно удалить из последовательности, то вывести $-X$ . Если в последовательность нужно добавить число $X$ , то вывести $+X$ . Если существует несколько вариантов с минимальным количеством действий, то можно вывести любой из них.

Пример ввода

5
2 1 4 1 100

Пример вывода

3
-1
-100
+3

Система оценки и описание подзадач

Подзадача 1 (50 баллов)

$1 <= N <= 1000$ , числа в диапазоне от 1 до 1000.

В этой подзадаче 5 тестов, каждый тест оценивается в 10 баллов. Баллы за каждый тест начисляются независимо.

Подзадача 2 (50 баллов)

$1 <= N <= 10^5$ , числа в диапазоне от 1 до $10^9$ .

Необходимые подзадачи: 1.

В этой подзадаче 5 тестов, каждый тест оценивается в 10 баллов. Баллы за каждый тест начисляются независимо.

По запросу сообщается результат окончательной проверки на каждом тесте.