Гра в дорозі
Limits: 2 sec., 256 MiB
Під час довгої поїздки на Всеукраїнську олімпіаду дуже просто перехвилюватися. Це може завадити вам показати себе на змаганні. Щоб цього не допустити, ми радимо вам у дорозі грати в різноманітні ігри. Звісно, ігри повинні бути розвиваючими та з програмістським нахилом.
Ось наприклад, є у вас послідовність з \(n\) цілих чисел \([a_1, a_2, \ldots, a_n]\). Назвемо слабкістю найбільше значення бідності серед усіх підвідрізків послідовності.
Бідність підвідрізка — це модуль суми його елементів.
Підвідрізок послідовності — це її неперервна підпослідовність.
Вам потрібно знайти таке дійсне число \(x\), що слабкість послідовності \([a_1-x, a_2-x, \ldots, a_n-x]\) буде мінімальною.
Допоможіть же собі, напишіть для цього програму.
Input
Перший рядок містить ціле число \(n\) — довжину послідовності.
Другий рядок містить \(n\) цілих чисел \(a_i\) — елементи послідовності.
Output
У єдиному рядку виведіть дійсне число — мінімальну можливу слабкість послідовності \([a_1-x, a_2-x, \ldots, a_n-x]\). Відповідь вважатиметься правильною, якщо її абсолютна чи відносна похибка не перевищуватиме \(10^{-4}\).
Constraints
\(40 \%\) тестів: \(1 \le n \le 100, |a_i| \le 10^4\),
\(60 \%\) тестів: \(1 \le n \le 10^5, |a_i| \le 10^6\).
Samples
| Input (stdin) | Output (stdout) |
|---|---|
| 3 4 -7 4 | 5.5 |
Notes
У прикладі з умови при \(z=-1.5\) ми отримаємо послідовність \([5.5, -5.5, 5.5]\).
Бідності підвідрізків такі: [1; 1] — 5.5; [2;2] — |-5.5|=5.5; [3;3] — 5.5; [1;2] — |5.5-5.5|=0; [2;3] — |-5.5+5.5|=0; [1;3] — |5.5-5.5+5.5|=5.5.
Отже, слабкість отриманої послідовності дорівнює 5.5. Це найменша можлива слабкість.
Submit a solution
| Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
|---|
| Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
|---|