Здравствуйте! На acmp.ru есть задача, которую я не могу сдать, а именно — пройти 29-й тест.
Кратко условие: есть циклический массив длины n (1 ≤ n ≤ 105) из целых неотрицательных чисел (все его элементы расположены по кругу), сумма элементов которого не превосходит 109. Требуется для каждого k от 1 до n определить, можно ли разбить отрезок [1..n] массива на k непересекающихся отрезков, сумма элементов в которых равна и каждый элемент покрыт хотя бы одним отрезком. Так как массив циклический, то за элементом с индексом n следует элемент с индексом 1, таким образом, последний отрезок может переходить через границу массива.
Мое решение: пусть сумма всех элементов массива равна S, k — количество отрезков, сумма в которых равна s. Тогда выполняется тождество S = s * k. Для каждого делителя S проверяю явно, можно ли сформировать k отрезков. Особый случай — когда сумма всех элементов равна 0, тогда возможны все значения k от 1 до n. Решение проходит 28 тестов, а на 29-м вердикт Wrong Answer.
Прошу сказать, почему мое решение не работает, или написать решение, которое прошло бы все тесты и с которым можно было бы сравнить. Заранее спасибо.
