E. Тонкая настройка

Задачу добавил: alef

Успешно сдано решений: 10

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

Чтобы обеспечить как можно более длительную эксплуатацию автоматической котельной, крайне желательно избегать резких перепадов температуры теплоносителя. Поэтому министерство науки планирует разработать график изменения температуры теплоносителя, опираясь на прогноз погоды на ближайшие $n$дней.

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

Более формально, рассмотрим график $g_1,g_2,\dots ,g_n$, в котором величин $g_j$ означает рекомендуемую температуру теплоносителя в день $\#j$. Рассмотрим все изменения температуры $|g_j-g_{j-1}|$ (взятые по абсолютному значению) и выберем из них наибольшее. Будем считать это число характеристикой графика. Среди всех графиков нужно выбрать тот, который обладает наименьшей характеристикой.

Во второй строке содержится $n$ целых чисел $w_1,w_2,\dots ,w_n$ $(-5\cdot {10}^8\le w_j\le 5\cdot {10}^8,j=1,2,\dots ,n)$, $w_j$ — уличная температура в день $\#j$.

11 20 30
-5 -8 -12 -7 5 8 2 -3 7 -4 -10

4
30 32 32 28 24 21 22 25 22 26 30 

Сдать задачу

Задать вопрос жюри по этой задаче