Не понимаю, что не так с моим решением
Difference between ru2 and ru3, changed 6 character(s)
Здравствуйте! На acmp.ru есть [задача](https://acmp.ru/asp/do/index.asp?main=task&id_course=3&id_section=25&id_topic=175&id_problem=1151) — самая сложная задача с полуфинала ВКОШП 2016/2017 Красноярского края, которую я не могу сдать. Прошу помочь разобраться, почему решение не проходит. Заранее спасибо.↵

Кратко условие: есть циклический массив длины $n$ $(1 \le n \le 10^5)$ из целых неотрицательных чисел (все его элементы расположены по кругу), сумма элементов которого не превосходит $10^9$. Требуется для каждого $k$ от $1$ до $n$ определить, можно ли разбить отрезок $[1..n]$ массива на $k$ непересекающихся отрезков, сумма элементов в которых равна и каждый элемент покрыт хотя бы одним отрезком. Так как массив циклический, то за элементом с индексом $n$ следует элемент с индексом $1$, таким образом, последний отрезок может переходить через границу массива.↵

[Мое решение](https://ideone.com/rgmJZC): пусть сумма всех элементов массива равна $S$, а $k$ — количество отрезков, сумма в которых равна $s$. Тогда выполняется тождество $S = s * k$. Для каждого делителя $S$ проверяю явно, можно ли сформировать $k$ отрезков. Особый случай: когда сумма всех элементов равна $0$, тогда возможны все значения $k$ от $1$ до $n$. Сначала проверяю, есть ли отрезок $[l, r)$ $(0 
<=\le l < r < n)$: $sum[l...r-1] = s$, затем от r до l прохожу, формируя остальные отрезки. Решение проходит 30 тестов, а на 31-м вердикт Wrong Answer.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
ru8 Russian dmkz 2018-06-15 16:10:10 1029
ru7 Russian dmkz 2018-06-14 23:29:23 1310 Мелкая правка: 't log(n)) ~ O(n^(4/3)' -> 't log(n)) \approx O(n^(4/3)'
ru6 Russian dmkz 2018-06-14 16:53:11 9
ru5 Russian dmkz 2018-06-14 16:51:16 1 Мелкая правка: '1.5 секунд следующее' -> '1.5 секунды следующее'
ru4 Russian dmkz 2018-06-14 16:37:33 436
ru3 Russian dmkz 2018-06-14 14:56:30 6 Мелкая правка: ', r)$ $(0 <= l < r < n' -> ', r)$ $(0 \le l < r < n'
ru2 Russian dmkz 2018-06-14 14:42:32 448
ru1 Russian dmkz 2018-06-14 12:49:26 1394 Первая редакция (опубликовано)