26 січня 2024 року відбувся III (обласний) етап Всеукраїнської учнівської олімпіади з інформатики Житомирської області. Учні-програмісти змагалися в розв’язанні задач на платформі «Contest Management System», розгорнутій в університеті «Житомирська політехніка».
Учасникам олімпіади було запропоновано сім задач і чотири години часу для їх розв’язання. Для контролю на всіх робочих місцях учасників було встановлено вебкамери, що в режимі онлайн транслювали зображення і звук для журі. Крім того, учасники проводили відеозапис екранів своїх комп’ютерів і по завершенню олімпіади передали журі покликання на чотиригодинні відеозвіти.
Після завершення олімпіади задачі традиційно з’явилися на сайті eolymp.com, всі бажаючі можуть тепер спробувати свої сили в їх розв’язанні.
Розглянемо одну з задач олімпіади — «Балансуючі елементи» (https://www.eolymp.com/uk/problems/11658).
Умова:
Задано послідовність з N елементів, які є цілими числами. Назвемо «балансуючим елементом» такий, що сума всіх елементів перед ним дорівнює сумі елементів після нього. При цьому перший та останній елементи послідовності не можуть бути «балансуючими».
Знайдіть кількість «балансуючих елементів» у заданій послідовності.
Вхідні дані:
У першому рядку записане ціле число N. У другому рядку записано N цілих чисел, розділених пробілом. Всі числа не перевищують за модулем 100000.
Вихідні дані:
Виведіть одне число – кількість «балансуючих елементів».
Приклад
Вхідні дані:
3
1 2 1
Вихідні дані:
1
— Ліміт часу: 1 секунда
— Ліміт використання пам'яті: 256 Mb
Зрозуміле формулювання задачі та знання програмістами функції SUM() при роботі зі списками створює багатьом солодку ілюзію рівня «я зараз цю задачу як Тузик ганчірку». Але, згідно статистики олімпіади, лише 22% учасників обласної олімпіади зробили її на 100%. Чому так мало? Мабуть, за це варто подякувати авторам задачі і тим, хто складав для неї тести.
Нескладно представити, як працює функція SUM(). Звичайно, це повний перебір елементів з додаванням їх значень. І, незважаючи, що всередині мови програмування функція максимально оптимізована, на її виконання потрібен деякий час.
Давайте представимо варіант, коли зліва і справа від елементу, що перевіряється, стоїть по мільйону елементів. Відповідно, для перевірки «балансовості» поточного елемента треба виконати SUM(мільйон елементів) для елементів, що стоять лівіше його і SUM(мільйон елементів) для елементів, що стоять правіше. Тобто, два мільйони елементів перебираються задля перевірки одного поточного. Далі беремося перевіряти на балансовість наступний елемент — і знову перебираємо два мільйони елементів. Але ж у нас на всю задачу ліміт в 1 секунду.
Якщо б автори задачі сформували лише невеличкі по розміру масиви-списки для тестів, то задачу би здали більше програмістів. А на великих списках одної секунди для розв’язку таким алгоритмом очікувано не вистачало. При чому як на Python, так і на C# (дякую за перевірку Захару з i7).
Хоча певні питання до укладачів тестів у нас є. Наприклад, восьмикласник Андрій з i7 вважає, що за розв’язок
print(1)
зараховувати цій задачі 30% - то багато. Як на мене — дійсно багато.
Але давайте спробуємо знайти алгоритм розв’язку задачі «Балансуючи елементи», що розв’яже її на 100% за секунду навіть на повільному Python.
Якщо ви хочете спробувати самостійно, то не читайте далі, а пробуйте.
Удачі!
Для тих відвідувачів «Плетива», що не знайшли рішення, після натискання на покликання «Детальніше» я запропоную свою версію і код.
Пропоную один раз визначити суму всіх елементів списку (suma).
Починаємо перебирати елементи від першого до передостаннього (нульовий і останній елементи, згідно умови, не можуть бути балансуючими). Розглянемо перший елемент. Значення елементу, що знаходиться лівіше від нього, додаємо до суми елементів, що знаходяться лівіше нього (left):
left += elements[current - 1]
Таким чином ми будемо поступово накопичувати суму елементів в left. І, якщо значення в left буде дорівнювати половині суми всіх елементів за виключенням поточного, то поточний елемент — балансуючий.
if suma - left * 2 == elements[current]:
count += 1
Таким алгоритмом ця задача здається на 100%.
Код:
n = int(input())
elements = [int(x) for x in input().split()]
count = 0
suma = sum(elements)
left = 0
for current in range(1, n - 1):
left += elements[current - 1]
if suma - left * 2 == elements[current]:
count += 1
print(count)