Лягушонок Билли сидел на камне и любовался на закат, когда понял, что проголодался. Он огляделся и с удивлением обнаружил, что в ручье около него копошатся мошки. Ручей представляет собой прямую, на которой расположен и камень, на котором сидит Билли. Лягушонок был очень голоден, и потому захотел съесть всех мошек. У Билли очень длинный язык, поэтому он может, не спрыгивая с камня, съесть любую мошку (но только одну за раз). Однако высовывать язык на большие расстояния не так-то просто, лягушонок на каждый сантиметр высунутого языка тратит одну единицу энергии. Каждый раз, когда Билли съедает мошку из какой-то точки происходит следующее: все мошки, сидящие слева от съеденной мошки, и все мошки, сидящие справа от нее в ужасе отпрыгивают от места событий на один сантиметр вдоль ручья. Мошки, которые сидят в той же точке, что и съеденная, настолько шокированы этим событием, что не двигаются.

Вы используете гостевой доступ (Вход)
Эврика: Задачи турнира 2018 г.
В начало
Курсы
Кружки и уроки
Камчатский край
Эврика
Тема 35
Задачи турнира 2018 г.
Задача №113668. Лягушонок Билли
Лягушонок Билли сидел на камне и любовался на закат, когда понял, что проголодался. Он огляделся и с удивлением обнаружил, что в ручье около него копошатся мошки. Ручей представляет собой прямую, на которой расположен и камень, на котором сидит Билли. Лягушонок был очень голоден, и потому захотел съесть всех мошек. У Билли очень длинный язык, поэтому он может, не спрыгивая с камня, съесть любую мошку (но только одну за раз).

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

Если мошка в какой-то момент времени прыгает на камень, где сидит Билли, то Билли тут же съедает ее не тратя энергии. При этом другие мошки не перемещаются.
Лягушонок Билли хочет понять — какое минимальное количество единиц энергии ему потребуется для того, чтобы съесть всех мошек ему это выяснить.

Входные данные
В первой строке входного файла задано одно натуральное числа n (1≤n≤100000) — количество мошек. Во второй строке входного файла задано n натуральных чисел — расстояния каждой из мошек до камня. Известно, что все мошки находятся на одной прямой по одну сторону от камня. Расстояния даны в порядке неубывания. Расстояния не превышают 109 .

Выходные данные
Выведите одно число — минимальное количество единиц энергии, которое потребуется Билли, чтобы съесть всех мошек.

Пояснение к примеру
Сначала Билли съест одну мошку, сидящую в точке 4. Другая мошка, сидящая в этой точке не сдвинется, обе мошки из точки 2 сдвинутся в точку 1. После того, как он съест вторую мошку в точке 4, обе мошки из точки 1 отпрыгнут в точку 0, где и будут сразу съедены.

260

321

Посмотреть ответы 1

Ответы на вопрос:

morvilous77

Информатика

4,6(9 оценок)

Например это множество арабских цифр [0,1,2,3,4,5,6,7,8,9]

Задай свой вопрос

Как otvet5GPT работает?

otvet5GPT использует большую языковую модель вместе с базой данных GPT для обеспечения высококачественных образовательных результатов. otvet5GPT действует как доступный академический ресурс вне класса.
Сколько это стоит?

Проект находиться на стадии тестирования и все услуги бесплатны.
Могу ли я использовать otvet5GPT в школе?

Конечно! Нейросеть может помочь вам делать конспекты лекций, придумывать идеи в классе и многое другое!
В чем отличия от ChatGPT?

otvet5GPT черпает академические источники из собственной базы данных и предназначен специально для студентов. otvet5GPT также адаптируется к вашему стилю письма, предоставляя ряд образовательных инструментов, предназначенных для улучшения обучения.