Подразделы

Другие разделы

Дата и время

05/04/2025 22:32:26

Авторизация

Задачи очного тура личного первенства

A. Браки по расчету B. Broken Sword: потерянный файл C. Кредитный калькулятор D. Draw Grid E. Морской бой F. Фантастическая 4 G. Go Scoring H. Среднее арифметическое I. Лабиринт

B. Broken Sword: потерянный файл

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

— Ха-ха-ха! – с расстановкой произнес сеньор Сузарро и скрылся за дверью в противоположном конце склада. В качестве сувенира он оставил бомбу с часовым механизмом, который немедленно начал отсчитывать последние минуты перед взрывом.

Между Джорджем Стоббартом и выходом стоит несколько штабелей ящиков одинакового размера. Кроме этого в помещении склада есть мостовой кран и конвейер, по которому в неизвестном направлении двигаются аналогичные ящики. Джордж может перебраться с одного штабеля на соседний, если разница в количестве ящиков в этих штабелях не превышает 2. С помощью мостового крана Джордж может поставить ящик из любого штабеля на конвейер или, наоборот, взять ящик с конвейера и поставить его в любой штабель.

Требуется определить минимальное число ящиков, которые нужно переместить, чтобы Джордж смог пробраться к выходу. Начало и конец пути находятся на уровне земли, нельзя добавлять новые штабели ящиков.

В первой строке ввода содержится одно целое число

$N$ (

$1\ ≤\ N\ ≤\ 1000$ ) – количество штабелей ящиков. Во второй строке содержатся

$N$ целых чисел в диапазоне от 0 до 100 – количество ящиков в

$i$ -м штабеле (

$1\ ≤\ i\ ≤\ N$ ).

Вывести одно целое число – минимальное количество перемещенных ящиков.

Пример ввода

4
1 5 4 3

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