Разбор задачи G. Взаиморасчеты

Тема: задача на идею, поиск инварианта
Сложность: сложная

В основу задачи положена задача M1258 из журнала Квант №12 за 1990г. (автор задачи О. Ижболдин).
Разбор решения задачи был опубликован в №12 за 1991г.

Для сведения задачи к рассмотренной в журнале и для избавления от дробных чисел выполним замену `a'_i=(a_i-S)*N`, где `S` – среднее арифметическое чисел `a_i`.
Среднее станет равным 0 и результат операции обмена будет иметь вид `a_{(i-1)\ mod\ N}+a_i,\ -a_i,\ a_{(i+1)\ mod\ N}+a_i`. При рассмотрении частичных сумм `b_i=∑_{j=0..i}\ a_j` можно обнаружить, что операция сводится к обмену значений `b_{i-1}` и `b_i`.
Таким образом, получение конечного распределения возможно, если последовательность частичных сумм для конечного распределения состоит из перемешанных произвольным образом чисел `b_i+d`, где `d` – некоторая константа, совпадающая с одним из `b_i` (при обмене с 1 человеком происходит сдвиг `b_i` по кругу). Константу легко найти с помощью сортировки частичных сумм для начального и конечного распределения.
Затем нужно привести последовательность частичных сумм для начального распределения в соответствие с последовательностью частичных сумм для конечного распределения с помощью обменов (аналог сортировки пузырьком).
Время работы алгоритма `O(N^2)`.