Числа на окружности

[MrDindows]

На окружности расставлено $N$ целых чисел $a_1, a_2, ..., a_n$. На каждом шаге разрешается выбрать одно отрицательное число, заменить его на его положительное значение, а от соседних двух отнять это значение. Необходимо определить, за какое наименьшее число шагов можно сделать так, чтоб все числа были неотрицательными (если это возможно, конечно).

Задача c олимпиады по программированию (SEERC 2014), и большинство команд чисто интуитивно угадали правильное решение: на каждом шаге брать самое маленькое число. Но как доказать его корректность?

[atlakatl]

MrDindows в сообщении #953679 писал(а):

если это возможно, конечно

Что за постановка задачи? Где критерий "возможно/невозможно"?
Общая сумма в процессе не меняется. Т.е. если она изначально меньше нуля, то цель не достижима.
При сумме равной нулю процесс может сойтись к цели, а может и зациклиться.
При положительной сумме проще выбирать ближайшее к нолю отрицательное число или меньшее по модулю, чем соседние положительные.

[Evgenjy]

Приведите, пожалуйста, оригинальный текст задачи, или дайте ссылку.

[Null]

Задача А

[Shadow]

atlakatl в сообщении #953857 писал(а):

При сумме равной нулю процесс может сойтись к цели, а может и зациклиться.

Не получится - последний ход невозможен.

MrDindows в сообщении #953679 писал(а):

и большинство команд чисто интуитивно угадали правильное решение: на каждом шаге брать самое маленькое число. Но как доказать его корректность?

В примере из файла 1,-2,-1,3 все равно какое число выбирается - всегда получается ровно за 9 шагов. Придумал пример с тремя числами - тоже самое. Интересно.

[atlakatl]

Shadow в сообщении #953926 писал(а):

Не получится - последний ход невозможен.

5, -4, -1
1, 4, -5
-4, -1, 5
4, -5, 1
-1, 5, -4

Пришли к начальной позиции. Это и есть зацикливание.

[ИСН]

Это - на здоровье. Сойтись не может.

[Null]

Там в условии задачи сумма строго положительная, и поэтому процесс конечен и не зависит от порядка операций.(Вроде получилось доказать). Надо посмотреть на бесконечную в обе стороны последовательность частичных сумм.

[Evgenjy]

Shadow в сообщении #953926 писал(а):

В примере из файла 1,-2,-1,3 все равно какое число выбирается - всегда получается ровно за 9 шагов. Придумал пример с тремя числами - тоже самое. Интересно.

У меня тоже есть подозрение, что число шагов не зависит от порядка ходов.

[MrDindows]

Хм, интересно получается.

Null в сообщении #953955 писал(а):

Там в условии задачи сумма строго положительная, и поэтому процесс конечен и не зависит от порядка операций.(Вроде получилось доказать). Надо посмотреть на бесконечную в обе стороны последовательность частичных сумм.

Не могли бы вы, пожалуйста, чуть подробней рассказать подход к доказательству?

[Null]

Пусть $s=a_1+\dots+a_N>0$
Пусть последовательность $a_k$ - бесконечная в обе стороны по правилу $a_{k+N}=a_k$.
Пусть $S_k$ -последовательность частичных сумм, $S_k=a_k+S_{k-1}$, тоже бесконечная в обе стороны.(Значение $S_0$ выбирается произвольно).
1. $L_r=(S_{r+Nt})$ - N арифметических прогрессий в разностью $s$.
2.Операция ограбления соседей банка $i$ равносильна перестановке последовательности $L_i$ на 1 влево.($S_0$ может поменяться, но нас интересуют разности.). $a_i<0$ равносильно $S_{i+Nt}<S_{i-1+Nt}$ - не зависит от $t$.
3.Ключевое наблюдение. Для каждой пары последовательностей $L_i$ и $L_j$ количество обменов фиксировано и не зависит от других последовательностей.(В итоге должна получиться $S_i$ - не убывающая последовательность) Соответственно искомое количество равно сумме по всем парам последовательностей количеств нужных обменов.