Problem:


Score : 300 points

Problem Statement

You are given an integer sequence of length N. The i-th term in the sequence is a_i.
In one operation, you can select a term and either increment or decrement it by one.

At least how many operations are necessary to satisfy the following conditions?

For every i (1≤i≤n), the sum of the terms from the 1-st through i-th term is not zero.

For every i (1≤i≤n-1), the sign of the sum of the terms from the 1-st through i-th term, is different from the sign of the sum of the terms from the 1-st through (i+1)-th term.

Constraints

2 ≤ n ≤ 10^5

|a_i| ≤ 10^9

Each a_i is an integer.

Input

Input is given from Standard Input in the following format:

n
a_1 a_2 ... a_n

Output

Print the minimum necessary count of operations.

Sample Input 1

4
1 -3 1 0

Sample Output 1

4

For example, the given sequence can be transformed into 1, -2, 2, -2 by four operations. The sums of the first one, two, three and four terms are 1, -1, 1 and -1, respectively, which satisfy the conditions.

Sample Input 2

5
3 -6 4 -5 7

Sample Output 2

0

The given sequence already satisfies the conditions.

Sample Input 3

6
-1 4 3 2 -5 4

Sample Output 3

8



Sample input:
4
1 -3 1 0


Sample output:
4

Submission status: Accepted

Solution code:
import itertools
n=int(input())
a=list(map(int,input().split()))
a=list(itertools.accumulate(a))
ans=0
buf=0
for i in range(n):
    if i%2==0:
        if a[i]+buf<=0:
            ans+=1-(a[i]+buf)
            buf+=1-(a[i]+buf)
    else:
        if a[i]+buf>=0:
            ans+=(a[i]+buf)+1
            buf-=(a[i]+buf)+1
x=ans
ans=0
buf=0
for i in range(n):
    if i%2==0:
        if a[i]+buf>=0:
            ans+=(a[i]+buf)+1
            buf-=(a[i]+buf)+1
    else:
        if a[i]+buf<=0:
            ans+=1-(a[i]+buf)
            buf+=1-(a[i]+buf)
print(min(x,ans))

Submission status: Accepted

Solution code:
n = int(input())
numbers = list(map(int,input().split()))
p = numbers[0]
a, b = 0, 0
if p > 0:
    q = -1
    b = p + 1
elif p < 0:
    q = 1
    b = -p + 1
else:
    p, q = 1, -1
    a, b = 1, 1
    
for i in range(1, n):
    if p > 0:
        p += numbers[i]
        if p >= 0:
            a += (p + 1)
            p -= (p + 1)
    else:
        p += numbers[i]
        if p <= 0:
            a -= (p - 1)
            p -= (p - 1)

for j in range(1, n):
    if q > 0:
        q += numbers[j]
        if q >= 0:
            b += (q + 1)
            q -= (q + 1)
    else:
        q += numbers[j]
        if q <= 0:
            b -= (q - 1)
            q -= (q - 1)


print(min(a, b))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

N = int(input())
As = list(map(int, input().split()))

results = []

ans = 0
sum_a = 0
flg = 1

for a in As:
    if flg == 1:
        if 1 <= sum_a + a:
            sum_a += a
        else:
            a_ = 1 - sum_a
            ans += 1 - sum_a - a
            sum_a = 1
        #print(a,sum_a,ans)
    else:
        if sum_a + a <= -1:
            sum_a += a
        else:
            a_ = -1 - sum_a
            ans += +1 + sum_a + a
            sum_a = -1
        #print(a,sum_a,ans)
    flg *= -1

results.append(ans)

ans = 0
sum_a = 0
flg = -1

for a in As:
    if flg == 1:
        if 1 <= sum_a + a:
            sum_a += a
        else:
            a_ = 1 - sum_a
            ans += 1 - sum_a - a
            sum_a = 1
        #print(a,sum_a,ans)
    else:
        if sum_a + a <= -1:
            sum_a += a
        else:
            a_ = -1 - sum_a
            ans += +1 + sum_a + a
            sum_a = -1
        #print(a,sum_a,ans)
    flg *= -1

results.append(ans)

print(min(results))

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))

def func(A, plus):
  total = A[0]
  ans = 0
  if plus:
    if A[0] <= 0:
      ans = abs(A[0])+1
      total = 1
  else:
    if A[0] >= 0:
      ans += abs(A[0])+1
      total = -1
  for a in A[1:]:
    t = total + a
    if total * t < 0:
      total = t
      continue
    ans += abs(t)+1
    total = -1 if total > 0 else 1
  return ans

print(min(func(A, True), func(A, False)))

Submission status: Accepted

Solution code:
n = int(input())
As = list(map(int, input().split()))

if As[0] > 0:
    acc0s = [As[0], -1]
    num0s = [0, As[0] + 1]
elif As[0] < 0:
    acc0s = [As[0], 1]
    num0s = [0, -As[0] + 1]
else:
    acc0s = [1, -1]
    num0s = [1, 1]

ans = float('inf')
for acc0, num0 in zip(acc0s, num0s):
    acc = acc0
    num = num0
    for a in As[1:]:
        if acc * (acc + a) < 0:
            acc += a
        else:
            if acc > 0:
                num += a - -(acc + 1)
                acc = -1
            else:
                num += -(acc - 1) - a
                acc = 1

    ans = min(ans, num)

print(ans)

Submission status: Accepted

Solution code:
#!usr/bim/python
#! -*- coding: utf-8 -*-

n = raw_input()
n = int(n)

a = raw_input()
a = a.split()
a = map(int,a)

#+-
goukei_1 = 0
sousa_1 = 0
for i in range(n):
    goukei_1 += a[i]
    if i % 2 == 0 and goukei_1 <= 0:
        sousa_1 += 1 + (-goukei_1)
        goukei_1 = 1
    elif i % 2 == 1 and goukei_1 >= 0:
        sousa_1 += 1 + goukei_1
        goukei_1 = -1

#-+
goukei_2 = 0
sousa_2 = 0
for i in range(n):
    goukei_2 += a[i]
    if i % 2 == 1 and goukei_2 <= 0:
        sousa_2 += 1 + (-goukei_2)
        goukei_2 = 1
    elif i % 2 == 0 and goukei_2 >= 0:
        sousa_2 += 1 + goukei_2
        goukei_2 = -1

print min(sousa_1, sousa_2)

Submission status: Accepted

Solution code:
N = int(input())
a = list(map(int, input().split()))
# N = 4
# a = [1, -3, 1, 0]
# N = 5
# a = [3, -6, 4, -5, 7]
# N =6
# a = [-1, 4, 3, 2, -5, 4]


def solve(start):
    cum_sum = 0
    cost = 0
    for i in range(N):
        cum_sum += a[i]
        if i % 2 == start:
            if cum_sum < 1:
                cost += 1 - cum_sum
                cum_sum = 1
        else:
            if cum_sum > -1:
                cost += (cum_sum + 1)
                cum_sum = -1
    return cost


ans = min(solve(start=0), solve(start=1))
print(ans)

Submission status: Accepted

Solution code:
# +-+-...と-+-+...をためす

N = int(input())
A = list(map(int, input().split()))

def solve(start_sgn):
  sgn = start_sgn
  r = 0
  s = 0
  for a in A:
    s += a
    if s*sgn <= 0:
      r += abs(s-sgn)
      s = sgn
    sgn *= -1
  return r

print(min(solve(1), solve(-1)))

Submission status: Accepted

Solution code:
#ARC72 C
n = int(input())
A = list(map(int, input().split()))
# print(A)

def get_ops(init_sign):
    prev_sign = init_sign
    sigma = A[0]
    operations = 0

    if A[0] == 0 and init_sign == '+':
        sigma = 1
        operations = 1
    elif A[0] == 0 and init_sign == '-':
        sigma = -1
        operations = 1
    elif A[0] > 0 and init_sign == '-':
        sigma = -1
        operations = A[0] + 1
    elif A[0] < 0 and init_sign == '+':
        sigma = 1
        operations = abs(A[0]) + 1
        
    for a in A[1:]:
        sigma += a
        if sigma >= 0 and prev_sign == '+':
            diff = sigma+1
            sigma -= diff
            operations += diff
        elif sigma <= 0 and prev_sign == '-':
            diff = abs(sigma)+1
            sigma += diff
            operations += diff
        if prev_sign == '+':
            prev_sign = '-'
        elif prev_sign == '-':
            prev_sign = '+'

    return operations

ops = 0
if A[0] > 0:
    ops = min(get_ops('+'), get_ops('-'))
elif A[0] < 0:
    ops = min(get_ops('+'), get_ops('-'))
else: # if A[0] is 0, try both case
    ops = min(get_ops('+'), get_ops('-'))

print(ops)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
ans = 10 ** 100
p = lambda x, y: x * y >= 0
po = lambda x, y: abs(x + y) + 1 if p(x, x + y) else 0
popo = lambda x, y: -1 * x // abs(x) if p(x, x + y) else x + y


if a[0] == 0:
    s = [1, -1]
    tmpAns = [1, 1]
    for (_s, _ans) in zip(s, tmpAns):
        for i in range(1, n):
            _ans +=  po(_s, a[i])
            _s = popo(_s, a[i])
        ans = min((ans, _ans))
else:
    s = [a[0], -1 * a[0] // abs(a[0])]
    tmpAns = [0, abs(a[0]) + 1]
    for (_s, _ans) in zip(s, tmpAns):
        for i in range(1, n):
            _ans +=  po(_s, a[i])
            _s = popo(_s, a[i])
        ans = min((ans, _ans))

print(ans)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()

def main():
    n = I()
    a = LI()
    r = 0
    c = 0
    for i in range(n):
        t = a[i]
        if i%2 == 0:
            if c+t > 0:
                c += t
            else:
                r += 1 - (c+t)
                c = 1
        else:
            if c+t < 0:
                c += t
            else:
                r -= -1 - (c+t)
                c = -1
    r2 = 0
    c = 0
    for i in range(n):
        t = a[i]
        if i%2 == 1:
            if c+t > 0:
                c += t
            else:
                r2 += 1 - (c+t)
                c = 1
        else:
            if c+t < 0:
                c += t
            else:
                r2 -= -1 - (c+t)
                c = -1

    return min(r,r2)


print(main())

Submission status: Accepted

Solution code:
n = int(input())
alist = list(map(int, input().split()))

is_positive = True
operation_count = 0


def run(is_positive):
    tmp_sum = 0
    operation_count = 0
    for a in alist:
        tmp_sum += a
        if is_positive:
            if tmp_sum <= 0:
                operation_count += -tmp_sum + 1
                tmp_sum = 1
        else:
            if tmp_sum >= 0:
                operation_count += tmp_sum + 1
                tmp_sum = -1
        is_positive = not is_positive
    return operation_count


print(min(run(True), run(False)))

Submission status: Accepted

Solution code:
N = int(input())
prog = list(map(int,input().split()))
def seq(prog,first_Ev=False):
    sign = -1 if first_Ev else 1
    if sign * prog[0] > 0:
        answer = 0
        result = prog[0]
    else:
        answer = abs(sign - prog[0])
        result = sign
    for i in prog[1:]:
        sign *= -1
        result += i
        if result * sign <= 0:
            answer += abs(sign - result)
            result = sign
    return answer
print(min(seq(prog),seq(prog,first_Ev=True)))

Submission status: Accepted

Solution code:
n = int(raw_input())
A = map(int, raw_input().split())

def calc(A):
    cnt = 0
    s = 0
    sig = -1
    for a in A:
        s += a
        if sig * s < 1:
            cnt += abs(sig - s)
            s = sig
        sig *= -1
    return cnt

v1 = calc(A)
v2 = calc(map(lambda n: -n, A))
print min(v1, v2)

Submission status: Accepted

Solution code:
n=int(raw_input())
a=map(int,raw_input().split())

def count(sign):
	_sum=0
	_count=0
	global n,a
	for num in a:
		_sum+=num
		if sign:
			if _sum>0:
				pass
			else:
				_count+=(1-_sum)
				_sum+=(1-_sum)
			sign=False
		else:
			if _sum<0:
				pass
			else:
				_count+=(_sum+1)
				_sum-=(_sum+1)
			sign=True
	return _count
				
		


if n==0:
	print 0
else:
	print min(count(True),count(False))

Submission status: Accepted

Solution code:
import sys

def solve():
    n = int(input())
    a = [int(i) for i in input().split()]

    v = a[0] if a[0] > 0 else 1
    ans1 = abs(a[0] - v)

    for i in range(1, n):
        if v * (v + a[i]) < 0:
            v += a[i]
            continue
        else:
            if v < 0:
                ans1 += abs(v + a[i] - 1)
                v = 1
            else:
                ans1 += abs(v + a[i] + 1)
                v = -1

    v = a[0] if a[0] < 0 else -1
    ans2 = abs(a[0] - v)

    for i in range(1, n):
        if v * (v + a[i]) < 0:
            v += a[i]
            continue
        else:
            if v < 0:
                ans2 += abs(v + a[i] - 1)
                v = 1
            else:
                ans2 += abs(v + a[i] + 1)
                v = -1

    ans = min(ans1, ans2)

    print(ans)

if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
import copy

n = int(input())
A = list(map(int,input().split()))

def solve(m, A):
    count = 0
    c = A[0]
    if m == 0 and c <= 0:
        c = 1
        count = abs(A[0]) + 1
    elif m == 1 and c >= 0:
        c = -1
        count = abs(A[0]) + 1

    for a in A[1:]:
        if c * (c+a) >= 0:
            count += abs(a+c) + 1
            c = -1 * c//abs(c);
        else:
            c += a
    return count

print(min(solve(0,A), solve(1,A)))

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
B = [A[0]]

for i in range(1, N):
    B.append(B[i - 1] + A[i])

BB = list(B)

# +, -
ans1 = 0
tmp1 = 0

for i in range(N):
    B[i] += tmp1
    # +
    if i % 2 == 0:
        if B[i] <= 0:
            ans1 += (1 - B[i])
            tmp1 += (1 - B[i])
            B[i] = 1
    # -
    else:
        if B[i] >= 0:
            ans1 += (B[i] + 1)
            tmp1 -= (B[i] + 1)
            B[i] = -1

# -, +
ans2 = 0
tmp2 = 0

for i in range(N):
    BB[i] += tmp2
    # -
    if i % 2 == 0:
        if BB[i] >= 0:
            ans2 += (BB[i] + 1)
            tmp2 -= (BB[i] + 1)
            BB[i] = -1
    # +
    else:
        if BB[i] <= 0:
            ans2 += (1 - BB[i])
            tmp2 += (1 - BB[i])
            BB[i] = 1

print(min(ans1, ans2))
if ans1 < 0 or ans2 < 0:
    raise("hoge")

Submission status: Accepted

Solution code:
N=int(input())
a=[int(i) for i in input().split()]
ans=[]
for mode in range(2):
	tempans=0
	sumA=0
	#print(sumA)
	for i in range(0,N):
		#above 0
		sumA+=a[i]
		if (i+mode)%2==0:
			if sumA<=0:
				tempans-=(sumA-1)
				sumA=1
		else:
			if sumA>=0:
				tempans+=(sumA+1)
				sumA=-1
		#print(sumA)
	ans.append(tempans)
print(min(ans))

Submission status: Accepted

Solution code:
n = int(raw_input())
aa = map(int, raw_input().split())


# start plus
ans1 = 0
sum1 = aa[0]

# start minus
ans2 = 0
sum2 = aa[0]

if sum1 <= 0:
  ans1 += abs(1 - sum1)
  sum1 = 1

if sum2 >= 0:
  ans2 += abs(-1 - sum2)
  sum2 = -1

for i in range(1,n):
  ai = aa[i]
  sum1 += ai
  sum2 += ai

  if i%2 == 0:
    if sum1 <= 0:
      ans1 += abs(1 - sum1)
      sum1 = 1
    if sum2 >= 0:
      ans2 += abs(-1 - sum2)
      sum2 = -1

  else:
    if sum1 >= 0:
      ans1 += abs(-1 - sum1)
      sum1 = -1
    if sum2 <= 0:
      ans2 += abs(1 - sum2)
      sum2 = 1

print min(ans1, ans2)

Submission status: Accepted

Solution code:
n=int(raw_input())
a=map(int,raw_input().split())
ans1=0
ans2=0
su1=a[0]
su2=a[0]
if a[0]==0:
    su1+=1
    su2-=1
    ans1=1
    ans2=1
if a[0]!=0:
    if a[0]>0:
        su2=-1
        ans2+=a[0]+1
    else:
        su2=1
        ans2+=-a[0]+1
for i in xrange(1,n):
    tmp=su1
    su1+=a[i]
    if su1*tmp<0:
        continue
    else:
        if su1==0 and tmp<0:
            ans1+=1
            su1+=1
        elif su1==0 and tmp>0:
            ans1+=1
            su1-=1
        elif tmp<0 and su1<0:
            ans1+=-su1+1
            su1=1
        elif tmp>0 and su1>0:
            ans1+=su1+1
            su1=-1
for i in xrange(1,n):
    tmp=su2
    su2+=a[i]
    if su2*tmp<0:
        continue
    else:
        if su2==0 and tmp<0:
            ans2+=1
            su2+=1
        elif su2==0 and tmp>0:
            ans2+=1
            su2-=1
        elif tmp<0 and su2<0:
            ans2+=-su2+1
            su2=1
        elif tmp>0 and su2>0:
            ans2+=su2+1
            su2=-1
print min(ans1,ans2)

Submission status: Accepted

Solution code:
import numpy as np
import math

n = int(input())
a = list(map(int,input().split()))

maenogoukei = a[0]
goukei = a[0]
kaisuu = 0

if goukei == 0:
	kaisuu += 1
	maenogoukei = -1 
	goukei = maenogoukei



for a_i in a[1:]:
	goukei += a_i
	if maenogoukei > 0 and goukei >= 0:
		kaisuu += goukei + 1
		goukei = -1
		maenogoukei = -1
	elif maenogoukei < 0 and goukei <= 0:
		kaisuu += -goukei + 1
		goukei = 1
		maenogoukei = 1
	else:
		maenogoukei += a_i




maenogoukei2 = a[0]
goukei2 = a[0]
kaisuu2 = 0

if goukei2 == 0:
	kaisuu2 += 1
	maenogoukei2 = 1 
	goukei2 = 1
else:
	kaisuu2 += abs(goukei2) + 1
	maenogoukei2 = - int(np.sign(a[0]))
	goukei2 = - int(np.sign(a[0]))


for a_i2 in a[1:]:
	goukei2 += a_i2
	if maenogoukei2 > 0 and goukei2 >= 0:
		kaisuu2 += goukei2 + 1
		goukei2 = -1
		maenogoukei2 = -1
	elif maenogoukei2 < 0 and goukei2 <= 0:
		kaisuu2 += -goukei2 + 1
		goukei2 = 1
		maenogoukei2 = 1
	else:
		maenogoukei2 += a_i2

print( min([kaisuu,kaisuu2]) )

Submission status: Accepted

Solution code:
n = input()
a = map(int, raw_input().split())

c = []
for i in xrange(2):
    if i == 0:
        p = True
    else:
        p = False

    cum = 0
    count = 0
    for j in xrange(n):
        cum += a[j]
        if p:
            if cum <= 0:
                count += (1 - cum)
                cum = 1
        else:
            if cum >= 0:
                count += - (-1 - cum)
                cum = -1
        p = not p
    c.append(count)
print min(c)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys
import os

n = int(input())

BASE = list(map(int, input().split()))
answers = []

for v in [0, 1]:
    A = BASE[:]

    # assume plus start
    sum_value = 0
    add_num = 0

    for i, a in enumerate(A):
        sum_value += a

        # 偶数項までの和は正
        if i % 2 == v:
            if sum_value <= 0:
                A[i] = A[i] - sum_value + 1
                add_num += (-sum_value + 1)
                sum_value = 1

        # 奇数までの和は負
        else:
            if sum_value >= 0:
                A[i] = A[i] - sum_value - 1
                add_num += (sum_value + 1)
                sum_value = -1
    #print(add_num)
    answers.append(add_num)

print(min(answers))

Submission status: Accepted

Solution code:
n = int(input())
xs = list(map(int, input().split()))
def cost(xs, neg=False):
    sign = -1 if neg else 1
    if sign * xs[0] > 0:
        ret = 0
        sum_ = xs[0]
    else:
        ret = abs(sign - xs[0])
        sum_ = sign
    for x in xs[1:]:
        sign *= -1
        sum_ += x
        if sum_ * sign <= 0:
            ret += abs(sign - sum_)
            sum_ = sign
    return ret

print(min(cost(xs), cost(xs, neg=True)))

Submission status: Accepted

Solution code:
N = int( input() )
A = list( map( int, input().split() ) )
s = 0
f = 0
for i in range( N ):
  s += A[ i ]
  x = s
  if i & 1: # -> -1
    if x < 0: continue
    s -= x - ( -1 )
    f += x - ( -1 )
  else:
    if x > 0: continue
    s += 1 - x
    f += 1 - x
s = 0
g = 0
for i in range( N ):
  s += A[ i ]
  x = s
  if ~i & 1: # -> -1
    if x < 0: continue
    s -= x - ( -1 )
    g += x - ( -1 )
  else:
    if x > 0: continue
    s += 1 - x
    g += 1 - x
print( min( f, g ) )

Submission status: Accepted

Solution code:
#import numpy as np

n = int(input())
a = list(map(int, input().split()))
#a = np.fromstring(input(), dtype=np.int32, sep=' ')

def calc(mode):
    d = 0
    s = 0
    for i in range(n):
        s += a[i]
        if (i+mode) & 1:
            if s >= 0:
                d += s + 1
                s = -1
        else:
            if s <= 0:
                d += abs(s) + 1
                s = 1
    return d


print(min(calc(0), calc(1)))

Submission status: Accepted

Solution code:
N = int(input())
As = list(map(int, input().split()))

pos = [(-1)**i for i in range(N)]
neg = [-(-1)**i for i in range(N)]
sp = 0
sn = 0
cp = 0
cn = 0
for i in range(N):
    A = As[i]
    sp += A
    if pos[i] * sp <= 0:
        cp += abs(sp) + 1
        sp = pos[i]
    sn += A
    if neg[i] * sn <= 0:
        cn += abs(sn) + 1
        sn = neg[i]

print(min(cp, cn))

Submission status: Accepted

Solution code:
def solve(N, A):
    a = A[0]
    ans = 0
    for i in xrange(1, N):
        if a > 0 and a + A[i] < 0:
            a = a + A[i]
        elif a > 0 and a + A[i] >= 0:
            ans += A[i] + a + 1
            a = -1
        elif a < 0 and a + A[i] > 0:
            a = a + A[i]
        else:
            ans += -(A[i]+a)+1
            a = 1
    return ans


N = input()
A = map(int, raw_input().split())

if A[0] == 0:
    A[0] = -1
    ans1 = solve(N, A) + 1
    A[0] = 1
    ans2 = solve(N, A) + 1
    print min(ans1, ans2)
else:
    ans1 = solve(N, A)
    if A[0] > 0:
        tmp = A[0] + 1
        A[0] = -1
    else:
        tmp = -A[0] + 1
        A[0] = 1
    ans2 = solve(N, A) + tmp
    print min(ans1, ans2)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
N = int(input())
As = list(map(int, input().split()))

def solve(As, first_target):
    ret = 0
    for i, a in enumerate(As):
        if i == 0:
            ret += abs(a - first_target)
            prev_sum = first_target
        else:
            curr_sum = prev_sum + a
            if prev_sum > 0 and curr_sum >= 0:
                ret += abs(curr_sum - (-1))
                curr_sum = -1
            elif prev_sum < 0 and curr_sum <= 0:
                ret += abs(curr_sum - 1)
                curr_sum = 1
            prev_sum = curr_sum
#            print("i, a, ret, curr_sum  = ", i, a, ret, curr_sum)
    return ret

ans1 = solve(As, 1)
ans2 = solve(As, -1)
ans3 = solve(As, As[0])
print(min(ans1, ans2, ans3))

Submission status: Accepted

Solution code:
import sys
import random

def rd():
        return sys.stdin.readline().rstrip()

def rdi():
        return [ int(x) for x in rd().split() ]

N = rd()
A = rdi()

def calc(s, sign, a):
        cnt = 0
        for i in range(len(a)):
                s += a[i]
                while s < 0 and sign < 0:
                        cnt += (1-s)
                        s = 1
                while s > 0 and sign > 0:
                        cnt += (s+1)
                        s = -1
                if s == 0:
                        cnt += 1
                        if sign < 0:
                                s = 1
                        else:
                                s = -1
                sign = s
        return cnt

if A[0] == 0:
        print 1+min(calc(1, 1, A[1:]), calc(-1, -1, A[1:]))
else:
        print min(calc(0, -1, A), calc(0, 1, A))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
def solve(a):
    s, res = 0, 0
    for i, ai in enumerate(a):
        ss = s
        ss += ai
        if ss == 0:
            ss = 1 if s < 0 else -1
            res += 1
        else:
            if s < 0 and ss < 0:
                res += abs(ss) + 1
                ss = 1
            if s > 0 and ss > 0:
                res += abs(ss) + 1
                ss = -1
        s = ss
    return res

n = int(raw_input())
a = map(int, raw_input().split()) 

if a[0] == 0:
    a[0] = 1
    ans = solve(a) + 1
    a[0] = -1
    ans = min(ans, solve(a) + 1)
else:
    ans = solve(a)
    tmp = abs(a[0]) + 1
    a[0] = 1 if a[0] < 0 else -1
    ans = min(ans, solve(a) + tmp)
print ans

Submission status: Accepted

Solution code:
n = int(raw_input())
a = [int(_) for _ in raw_input().split()]
if a[0] == 0:
    ts = [1, -1]
    anss = [1, 1]
elif a[0] > 0:
    ts = [a[0], -1]
    anss = [0, a[0] + 1]
else:
    ts = [a[0], 1]
    anss = [0, -a[0] + 1]
for j in xrange(2):
    t = ts[j]
    ans = anss[j]
    for i in xrange(1, n):
        b = cmp(t, 0)
        t += a[i]
        c = cmp(t, 0)
        d = 0
        if b == c or c == 0:
            d = -t - 1 if b == 1 else -t + 1
            ans += abs(d)
            t += d
    ts[j] = t
    anss[j] = ans

print min(anss)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))

lis = [pow(-1,i) for i in range(n)]

res1 = 0
s1 = 0
for i in range(n):
	s1 += a[i]
	if lis[i] == 1:
		if s1 <= 0:
			res1 += 1 - s1
			s1 = 1
	else:
		if s1 >= 0:
			res1 += s1 + 1
			s1 = -1

lis = [pow(-1,i)*(-1) for i in range(n)]

res2 = 0
s2 = 0
for i in range(n):
	s2 += a[i]
	if lis[i] == 1:
		if s2 <= 0:
			res2 += 1 - s2
			s2 = 1
	else:
		if s2 >= 0:
			res2 += s2 + 1
			s2 = -1

print(min(res1,res2))

Submission status: Accepted

Solution code:
n = int(input())
ar = list(map(int,input().split()))
su = [0]*n
su[0]=ar[0]
for i in range(1,n):
    su[i] = ar[i] + su[i-1]

# +
ans1,off = 0,0
for i in range(0,n):
    if i%2 == 0:
        if su[i] + off <= 0:
            ans1 += 1-(su[i]+off)
            off += 1-(su[i]+off)
    else:
        if su[i] + off >= 0:
            ans1 += (su[i]+off+1)
            off -= (su[i]+off+1)

# -
ans2,off = 0,0
for i in range(0,n):
    if i%2 != 0:
        if su[i] + off <= 0:
            ans2 += 1-(su[i]+off)
            off += 1-(su[i]+off)
    else:
        if su[i] + off >= 0:
            ans2 += (su[i]+off+1)
            off -= (su[i]+off+1)
print(min(ans1,ans2))

Submission status: Accepted

Solution code:
from sys import exit, setrecursionlimit
from functools import reduce
from itertools import *
from collections import defaultdict
from bisect import bisect

def read():
  return int(input())

def reads():
  return [int(x) for x in input().split()]

setrecursionlimit(1000000)

n = read()
a = reads()

result = 10**16

sig = (1, -1)

count = 0
psum = 0
for i in range(n):
  psum += a[i]
  if psum * sig[i%2] <= 0:
    count += 1 - psum * sig[i%2]
    psum = sig[i%2]

result = count

count = 0
psum = 0
for i in range(n):
  psum += a[i]
  if psum * sig[(i+1)%2] <= 0:
    count += 1 - psum * sig[(i+1)%2]
    psum = sig[(i+1)%2]

result = min(result, count)

print(result)

Submission status: Accepted

Solution code:
n = input()
a = map(int, raw_input().split())
ans = 10**20
for p in range(2):
    s = 0
    x = [1, -1][p]
    c = 0
    for i in range(n):
        s += a[i]
        if x>0 and s<=0:
            c += 1-s
            s = 1
        elif x<0 and s>=0:
            c += s+1
            s = -1
        x = -x
    ans = min(ans, c)
print ans

Submission status: Accepted

Solution code:
# C
n = int(input())
A = list(map(int, input().split()))
res_1 = 0
res_2 = 0

# first < 0
som_1 = 0
for i in range(n):
    if i % 2 == 1:
        som_1 += A[i]
        if som_1 >= 0:
            res_1 += (som_1 + 1)
            som_1 = -1
    else:
        som_1 += A[i]
        if som_1 <= 0:
            res_1 += (-som_1 + 1)
            som_1 = 1
# first > 0
som_2 = 0
for i in range(n):
    if i % 2 == 0:
        som_2 += A[i]
        if som_2 >= 0:
            res_2 += (som_2 + 1)
            som_2 = -1
    else:
        som_2 += A[i]
        if som_2 <= 0:
            res_2 += (-som_2 + 1)
            som_2 = 1
print(min([res_1, res_2]))

Submission status: Accepted

Solution code:
n = input()
A = map(int, raw_input().split())

def func(plus):
    res = su = 0
    for i in xrange(n):
        su += A[i]
        if plus:
            if su <= 0:
                res += (1-su)
                su = 1
        else:
            if su >= 0:
                res += (su+1)
                su = -1
        plus ^= 1
    return res
print min(func(0), func(1))

Submission status: Runtime Error

Solution code:
import sys


def func(lst, sign):
  cur, res = 0, 0
  for i in alst:
    cur += i
    if sign and cur <= 0:
      res += abs(cur) + 1
      cur = 1
    elif not sign and cur >= 0:
      res += abs(cur) + 1
      cur = -1
    sign = not sign
  return res


def main():
  n, *alst = map(int, sys.stdin.read().split())
  print(min(func(alst, True), func(alst, False)))


if __name__ == '__main__':
  main()

Submission status: Runtime Error

Solution code:
n = int(input())
a = list(map(int, input().split()))

tmp = 0
ans = 0

if a[0] != 0:
    for i in range(n):
        if i == 0 :
            tmp += a[i]
        elif i % 2 == 1:
            tmp += a[i]
            if a[0] > 0:
                if tmp < 0 :
                    pass
                elif tmp >= 0 :
                    ans += (abs(tmp) + 1)
                    tmp = -1
            elif a[0] < 0:
                if tmp <= 0 :
                    ans += (abs(tmp)+1)
                    tmp = 1
                elif tmp > 0 :
                    pass
        elif i % 2 == 0:
            tmp += a[i]
            if a[0] > 0:
                if tmp > 0 :
                    pass
                elif tmp <= 0 :
                    ans += (abs(tmp) + 1)
                    tmp = 1
            elif a[0] < 0:
                if tmp >= 0 :
                    ans += (abs(tmp)+1)
                    tmp = -1
                elif tmp < 0 :
                    pass


elif a[0] == 0:
    ans_list = []
    a[0] = 1
    ans += 1
    for i in range(n):
        if i == 0 :
            tmp += a[i]
        elif i % 2 == 1:
            tmp += a[i]
            if a[0] > 0:
                if tmp < 0 :
                    pass
                elif tmp >= 0 :
                    ans += (abs(tmp) + 1)
                    tmp = -1
            elif a[0] < 0:
                if tmp <= 0 :
                    ans += (abs(tmp)+1)
                    tmp = 1
                elif tmp > 0 :
                    pass
        elif i % 2 == 0:
            tmp += a[i]
            if a[0] > 0:
                if tmp > 0 :
                    pass
                elif tmp <= 0 :
                    ans += (abs(tmp) + 1)
                    tmp = 1
            elif a[0] < 0:
                if tmp >= 0 :
                    ans += (abs(tmp)+1)
                    tmp = -1
                elif tmp < 0 :
                    pass  
    ans_list.append(ans)


    a[0] = -1
    ans += 1
    for i in range(n):
        if i == 0 :
            tmp += a[i]
        elif i % 2 == 1:
            tmp += a[i]
            if a[0] > 0:
                if tmp < 0 :
                    pass
                elif tmp >= 0 :
                    ans += (abs(tmp) + 1)
                    tmp = -1
            elif a[0] < 0:
                if tmp <= 0 :
                    ans += (abs(tmp)+1)
                    tmp = 1
                elif tmp > 0 :
                    pass
        elif i % 2 == 0:
            tmp += a[i]
            if a[0] > 0:
                if tmp > 0 :
                    pass
                elif tmp <= 0 :
                    ans += (abs(tmp) + 1)
                    tmp = 1
            elif a[0] < 0:
                if tmp >= 0 :
                    ans += (abs(tmp)+1)
                    tmp = -1
                elif tmp < 0 :
                    pass  

        ans_list.append(ans)
        ans = min(ans)

print(ans)