Codeforces Round 580 (Div. 2) |
---|
Закончено |
Даны $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$. За одну монету можно сделать следующую операцию:
Выбрать одно из этих чисел, и уменьшить или увеличить его на $$$1$$$.
В частности, мы можем применять эту операцию к одному и тому же числу несколько раз.
Мы хотим добиться того, чтобы произведение всех чисел стало равно $$$1$$$, другими словами, чтобы $$$a_1 \cdot a_2$$$ $$$\dots$$$ $$$\cdot a_n = 1$$$.
К примеру, для $$$n = 3$$$ и чисел $$$[1, -3, 0]$$$ мы можем сделать произведение равным $$$1$$$ за $$$3$$$ монеты: добавить $$$1$$$ к второму элементу, добавить $$$1$$$ к второму элементу еще раз, отнять $$$1$$$ от третьего элемента, в результате чего массив станет равным $$$[1, -1, -1]$$$. А $$$1\cdot (-1) \cdot (-1) = 1$$$.
Какое минимальное количество монет нужно для этого заплатить?
Первая строка содержит одно целое число $$$n$$$ ($$$1 \le n \le 10^5$$$) — количество чисел.
Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$-10^9 \le a_i \le 10^9$$$) — сами числа.
Выведите единственное число — минимальное количество монет, которое нужно потратить, чтобы сделать произведение равным $$$1$$$.
2 -1 1
2
4 0 0 0 0
4
5 -5 -3 5 3 0
13
В первом примере, вы можете изменить $$$1$$$ на $$$-1$$$ или $$$-1$$$ на $$$1$$$ за $$$2$$$ монеты.
Во втором примере, вы должны применить по крайней мере $$$4$$$ операции, чтобы произведение не было равным $$$0$$$.
В третьем примере, вы можете изменить $$$-5$$$ на $$$-1$$$ за $$$4$$$ монеты, $$$-3$$$ на $$$-1$$$ за $$$2$$$ монеты, $$$5$$$ на $$$1$$$ за $$$4$$$ монеты, $$$3$$$ на $$$1$$$ за $$$2$$$ монеты, $$$0$$$ на $$$1$$$ за $$$1$$$ монету.
Название |
---|