Темою випуску є чудова задача, представлена на ІІІ етапі Всеукраїнської олімпіади з інформатики в Житомирській області 26 січня 2024 р.

Балансуючі елементи:

https://basecamp.eolymp.com/uk/problems/11658

Умова:

Задано послідовність з N елементів, які є цілими числами. Назвемо «балансуючим елементом» такий, що сума всіх елементів перед ним дорівнює сумі елементів після нього. При цьому перший та останній елементи послідовності не можуть бути «балансуючими».

Знайдіть кількість «балансуючих елементів» у заданій послідовності.

Вхідні дані

У першому рядку записане ціле число N. У другому рядку записано N цілих чисел, розділених пробілом. Всі числа не перевищують за модулем 100000.

Вихідні дані

Виведіть одне число – кількість «балансуючих елементів».

Приклади

Вхідні дані #1

3

1 2 1

Відповідь #1

1

Звичайно, ми можемо розмістити елементи  у список, що дозволить зручно їх опрацьовувати.

Один з очевидних підходів полягає у виборі потенційно балансуючого елемента, починаючи від другого і до передостаннього і розрахунку суми елементів зліва від нього і справа від нього. Якщо ці дві суми співпадають, то елемент є «балансуючим» і ми збільшуємо лічильник «балансуючих» елементів.

Головна проблема такого підходу полягає в тому, що ми при аналізі кожного потенційно балансуючого елемента необхідно двічі виконати операцію підрахунку суми елементів, зліва і справа. А це займає багато часу. І тому код на основі такого алгоритму не проходить по часу всі тести. На Python точно не проходить. Чудово, що автори задачі так підібрали тести, що це мотивує шукати більш оптимальні розв'язки.

Наступний алгоритм, більш оптимальний, полягає в  тому, що при аналізі ми можемо не рахувати суму елементів з одного з боків. На початку програми ми можемо один раз підрахувати суму всіх елементів. А далі обирати циклом потенційного кандидата на роль балансуючого елемента і рахувати суму елементів, наприклад, лише зліва від нього. Тоді, якщо елемент, що розглядається, дійсно балансуючий, то загальна сума всіх елементів, мінус значення самого елементу, повинні дорівнювати подвійній сумі зліва. Це і буде означати, що сума зліва дорівнює сумі справа. Але і тут у нас при аналізі кожного елементу буде потрібно рахувати суму всіх елементів зліва від нього. А це також не швидко. Автори задачі знову чудово підібрали тести і Python-код на основі даного алгоритму не розв’язує повністю задачу за визначений час.

Розглянемо ще біль оптимальний алгоритм.  Ми взагалі не будемо при аналізі кожного елементу рахувати суму зліва. Давайте визначимо якусь змінну, наприклад «left», в якій будемо накопичувати суму елементів зліва від того, що наразі аналізується. Коли ми перейдемо до наступного елемента, ми просто додамо до значення змінної «left» значення одного єдиного елемента, того що лівіше. Це  буде значно швидше. Переглянувши всі елементи з другого до передостаннього, накопичуючи значення змінної  «left» і маючи один раз пораховану на початку програми суму всіх елементів, ми за визначений час розв’яжемо задачу на 100%.

Кода не буде, якщо у вас не виходить це розписати, питайте.

Успіхів!