10/04/2025 23:08:22

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

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

Задачи

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

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

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

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

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

Задачи

2827. Склад

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

Егор работает на складе. Каждый день ему поступают $N$ заказов на получение цепей из заданного количества звеньев $L_i$ . Обычно Егор отматывает от бесконечной катушки с цепью $L_i$ звеньев, разгибает $L_i$ -ое звено, чтобы отцепить цепь от катушки, затем сгибает снова это звено, получая цепь нужной длины. Марина предложила Егору разгибать $L_i+1$ -ое звено, но при этом к концу дня у Егора будут оставаться $N$ одиночных разогнутых звеньев. Егор хотел бы, чтобы после выполнения всех заказов, у него не оставалось одиночных звеньев. Из них можно собирать некоторые цепи, выбрав правильный порядок выполнения заказов.

Напишите программу, которая определяет минимальное количество звеньев, которые придется разогнуть и согнуть Егору.

В первой строке ввода содержится единственное целое число $N$ ( $1<=N<=10^5$ ) – количество заказов. Во второй строке ввода содержатся $N$ целых чисел $L_i$ ( $1 <= L_i <= 10^5$ ) – длина цепи в $i$ -ом заказе.

Выведите единственное целое число – минимальное количество звеньев, которые нужно разогнуть и согнуть.

Пример ввода

5
5 2 4 6 1

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

Пояснение к примеру: Егор может отделить цепи длиной 5, 4, 6 по способу, предложенному Мариной, а из 3 одиночных звеньев сделать цепи длиной 2 и 1. Это на 2 звена меньше, чем при способе, который он использовал ранее.

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

1
5

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

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

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

$1<=N<=100$

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

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

Ограничения из условий задачи.

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

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

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