Пікнік (Розбір)

Автор: Андрій Холод

Роздробник: Павло Цікалишин

Розбір підготовано: Костянтин Денисов

Потрібно розбити масив a_1,\dots,a_n на m=k+1 послідовних частин так, щоб сума в кожній частині була однакова, і використати всі шматки. Нехай S=\sum_{i=1}^n a_i. Тоді кожна частина має вагу T=S/m, отже обов'язково m \mid S.

Через те, що n \le 5000, можна зробити дуже просту перевірку: перебрати всі можливі $m$ від найбільшого до $1$ і перевірити, чи можна нарізати на $m$ частин сумою $T$ жадібно зліва направо. Оскільки ми знаємо наперед суму в кожній частині, то далі перший відрізок визначається однозначно, за ним другий і так далі.

Перевірка для фіксованого $m$. Обчислюємо T=S/m і йдемо по масиву, накопичуючи $cur$ та підраховуючи кількість друзів $cnt$:

• cur := cur + a_i.

• якщо cur = T, то "закриваємо" частину: cnt := cnt + 1, cur := 0;

• якщо cur > T, то таке $m$ неможливе (бо всі a_i \ge 1 і ми вже перебрали суму).

В кінці потрібно, щоб cur=0 і cnt=m.

Складність. Перебираємо $m$ не більше ніж $n$ разів, кожна перевірка за $O(n)$, отже загалом O(n^2). За n \le 5000 це проходить. Пам'ять $O(n)$.