Аморальні екcперименти
Обмеження: 2 сек., 256 МіБ
Щоб розробити ефективну вакцину від реп’яховірусу, потрібно розуміти, наскільки швидко він розповсюджується. Провідні українські вчені — Зеник та Марічка — проводять різноманітні експерименти, щоб краще розуміти закономірності розповсюдження вірусу.
Цього разу вони розсадили \(n\) людей за круглим столом. Для кожної людини відомо, чи вона заражена на початку експерименту. Зеник припускає, що якщо людина хвора, то рівно за одну хвилину вона заражає людей, що сидять поряд з нею за столом.
Якщо припущення Зеника правильне, то через скільки часу всі люди за столом будуть зараженими?
Вхідні дані
У першому рядку задано ціле число \(n\) — кількість людей, що беруть участь в експерименті.
У другому рядку задано \(n\) чисел 0 або 1. 1 означає, що відповідний учасник експерименту є хворим на початку експерименту, 0 — здоровим.
Вихідні дані
У єдиному рядку виведіть ціле число — мінімальний час, через який усі учасники експерименту захворіють, якщо припущення Зеника є правильним.
Обмеження
\(1 \le n \le 10^5\),
на початку експерименту є щонайменше один заражений учасник.
Приклади
| Вхідні дані (stdin) | Вихідні дані (stdout) |
|---|---|
| 7 1 0 0 0 1 0 1 | 2 |
Примітки
Після першої хвилини лише третій учасник буде здоровим, після другої — усі заражені.
Надіслати розв'язок
| Element Type | Створено | Хто | Задача | Компілятор | Результат | Час (сек.) | Пам'ять (МіБ) | № | Дії |
|---|
Аморальні експерименти - Розбір
Усіх людей за столом можна розділити на проміжки (тут проміжком називається множина людей, що сидять підряд), такі що кожен проміжок є або повністю зараженим, або повністю не зараженим. Зауважте, що оскільки стіл круглий, то перший учасник є сусідом останнього. Наприклад, стіл з восьми учасників {0 1 1 0 0 0 1 0} ділиться на 4 проміжки:
незаражений проміжок довжини 2, що включає першого та останнього учасника,
заражений проміжок довжини 2, що включає другого та третього учасника,
незаражений проміжок довжини 3, що включає учасників з четвертого по шостого,
заражений проміжок довжини один, що включає лише сьомого учасника.
.
Зрозуміло, що кожен незаражений проміжок ставатиме коротшим на два кожної хвилини, оскільки два крайні учасники заразяться від сусідніх заражених. Тобто, проміжок довжини \(k\) повністю заразиться за \(\lceil \frac{k}{2} \rceil\) хвилин. Усі учасники за столом захворіють, як тільки повністю заразиться найдовший з незаражених проміжків.
Отже, все що потрібно зробити — це знайти довжину найдовшого незараженого проміжку за круглим столом. Один зі способів це зробити такий: повторимо початковий масив двічі і просто знайдемо довжину найдовшого незараженого проміжку так, якби учасники сиділи не за круглим столом, а просто в рядок.
Складність розв’язку — \(O(n)\).
| Element Type | Створено | Хто | Задача | Компілятор | Результат | Час (сек.) | Пам'ять (МіБ) | № | Дії |
|---|