Автор задачі: | Тимкович Олександр |
Задачу підготував: | Ціцей Павло, Тимкович Олександр |
Розбір написав: | Тимкович Олександр |
Для зручності, зробимо індексацію з нуля, тобто a_0, a_1, \dots, a_{n-1}. Таке перетворення досить зручно в задачах з циклічними масивами, тому що ми можемо брати сусідні значення як (a_i, a_{(i+1)\bmod n}).
Нехай розчарування всіх друзів, не включаючи Сакурако, це , що можна порахувати на перед. Будемо перебирати позицію Сакурако, тобто кожну пару сусідніх друзів і Сакурако між ними. Як зміниться , якщо ми туди всунемо Сакурако? Потрібно від відняти розчарування, яке було між цією парою друзів, та додати два нові розчарування, отримані з Сакурако.