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: 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
    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
    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)

Submission status: Runtime Error

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

ans = 0


sum_A = A[0]
for i in range(1,N) :
    if ((sum_A + A[i]) == 0) or (sum_A *(sum_A + A[i]) >= 0) :
        if sum_A > 0 :
            ans += 1 + sum_A + A[i]
            #print("ans += {}".format(1 + sum_A + A[i]))
            sum_A = -1
        elif sum_A < 0 :
            ans += 1 - (sum_A + A[i])
            #print("ans += {}".format(1 - (sum_A + A[i])))
            sum_A = 1
        
    else :
        sum_A += A[i]
        #print("else")
    record.append(sum_A)

print(ans)

Submission status: Runtime Error

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


def solve(i, s, k, sign):
    if i >= len(A):
        return k

    if sign * (s + A[i]) > 0:
        return solve(i + 1, s + A[i], k, sign * -1)
    else:
        return solve(i + 1, sign, k + abs(s + A[i]) + 1, sign * -1)


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

Submission status: Runtime Error

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


def solve(i, s, k, sign):
    if i >= N:
        return k

    if sign * (s + A[i]) > 0:
        return solve(i + 1, s + A[i], k, sign * -1)
    else:
        return solve(i + 1, sign, k + abs(s + A[i]) + 1, sign * -1)


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

Submission status: Runtime Error

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


def solve(i, s, k, sign):
    if i == N:
        return k

    if sign * (s + A[i]) > 0:
        return solve(i + 1, s + A[i], k, sign * -1)
    else:
        return solve(i + 1, sign, k + abs(s + A[i]) + 1, sign * -1)


a = solve(0, 0, 0, 1)
b = solve(0, 0, 0, -1)

print(a)

Submission status: Runtime Error

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


def solve(i, s, k, sign):
    if i == N:
        return k

    if sign * (s + A[i]) > 0:
        return solve(i + 1, s + A[i], k, sign * -1)
    else:
        return solve(i + 1, sign, k + abs(s + A[i]) + 1, sign * -1)


a = solve(0, 0, 0, 1)
b = solve(0, 0, 0, -1)

if a < b:
    print(a)
else:
    print(b)

Submission status: Runtime Error

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


def solve(i, s, k, sign):
    if i == N:
        return k

    if sign * (s + A[i]) > 0:
        return solve(i + 1, s + A[i], k, sign * -1)
    else:
        return solve(i + 1, sign, k + abs(s + A[i]) + 1, sign * -1)


try:
    print(min(solve(0, 0, 0, 1), solve(0, 0, 0, -1)))
except TypeError:
    print(1)

Submission status: Runtime Error

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


def solve(i, s, k, sign):
    if i == N:
        return k

    if sign * (s + A[i]) > 0:
        return solve(i + 1, s + A[i], k, sign * -1)
    else:
        return solve(i + 1, sign, k + abs(s + A[i]) + 1, sign * -1)


try:
    print(min(solve(0, 0, 0, 1), solve(0, 0, 0, -1)))
except ValueError:
    print(1)

Submission status: Runtime Error

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


def solve(i, s, k, sign):
    if i == N:
        return k

    if sign * (s + A[i]) > 0:
        return solve(i + 1, s + A[i], k, sign * -1)
    else:
        return solve(i + 1, sign, k + abs(s + A[i]) + 1, sign * -1)


try:
    print(min(solve(0, 0, 0, 1), solve(0, 0, 0, -1)))
except IndexError:
    print(1)

Submission status: Runtime Error

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


def solve(i, s, k, sign):
    if i == N:
        return k

    if sign * (s + A[i]) >= 0:
        return solve(i + 1, s + A[i], k, sign * -1)
    else:
        return solve(i + 1, sign, k + abs(s + A[i]) + 1, sign * -1)


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

Submission status: Runtime Error

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


def solve(i, s, k, plus):
    if i == N:
        return k

    if plus:
        if s + A[i] <= 0:
            return solve(i + 1, 1, k + abs(s + A[i]) + 1, False)
        else:
            return solve(i + 1, s + A[i], k, False)
    else:
        if s + A[i] >= 0:
            return solve(i + 1, -1, k + abs(s + A[i]) + 1, True)
        else:
            return solve(i + 1, s + A[i], k, True)


print(min(solve(0, 0, 0, True), solve(0, 0, 0, False)))

Submission status: Runtime Error

Solution code:
X,Y=map(int,input().split())
if abs(X-Y)<=1:
  print("Brown")
else:
  print("Alice")

Submission status: Runtime Error

Solution code:
n = int(input())
lis = list(map(int,input().split()))
cou = 0
co = 0
ans1 = 0
ans2 = 0
for i in range(n):
  cou += lis[i]
  co += lis[i]
  if cou <= 0 and i % 2 == 0:
    ans1 += (1 -cou)
    cou = 1
  if cou => 0 and i % 2 == 1:
    ans1 += (cou +1)
    cou = -1
  if co => 0 and i % 2 == 0:
    ans2 += (co +1)
    co = -1
  if co <= 0 and i % 2 == 1:
    ans2 += (1 -co)
    co = 1
print(min(ans1,ans2))

Submission status: Runtime Error

Solution code:
N = int(input())
A = [int(_) for _ in input().split()]

def calc(A, y):
    result = abs(A[0] - y)
    t = y
    for a in A[1:N]:
        tt = t + a
        if t * tt >= 0:
            m =  -t // abs(t)
            result += abs(m - tt)
            tt = m
        t = tt
    return result

result = min(calc(A, A[0]), calc(A, -A[1]-1),  calc(A, -A[1]+1))

print(result)

Submission status: Runtime Error

Solution code:
import numpy as np


def dp(i,n):
    if i == 0:
        if a[0] == 0:
            if n == 1:
                return 1,1
            elif np.sign(a[1]) != 0:
                return -1 * np.sign(a[1]), 1
            else:
                return 1,1
        else:
            return a[0],0
    else:
        sg,count = dp(i-1,n)
        if np.sign(sg) == -1 * np.sign(sg+a[i]):
            return sg+a[i], count
        elif np.sign(sg) == 1:
            delta = abs(-1 - (sg + a[i]))
            return -1,count+delta
        else:
            delta = abs(1 - (sg + a[i]))
            return 1,count+delta


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

out_1,out_2 = dp(n-1,n)
print(out_2)

Submission status: Runtime Error

Solution code:
import numpy as np


def dp(i,n):
    if i == 0:
        if a[0] == 0:
            if n == 1:
                return 1,1
            elif np.sign(a[1]) != 0:
                return -1 * np.sign(a[1]), 1
            else:
                return 1,1
        else:
            return a[0],0
    else:
        sg,count = dp(i-1,n)
        if np.sign(sg) == -1 * np.sign(sg+a[i]):
            return sg+a[i], count
        elif np.sign(sg) == 1:
            delta = abs(-1 - (sg + a[i]))
            return -1,count+delta
        else:
            delta = abs(1 - (sg + a[i]))
            return 1,count+delta


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

print(dp(n-1,n)[1])

Submission status: Runtime Error

Solution code:
import numpy as np


def dp(i):
    if i == 0:
        if a[0] == 0:
            if n == 1:
                return 1,1
            else:
                return -1 * np.sign(a[1]), 1
        else:
            return a[0],0
    else:
        sg,count = dp(i-1)
        if np.sign(sg) == -1 * np.sign(sg+a[i]):
            return sg+a[i], count
        elif np.sign(sg) == 1:
            delta = abs(-1 - (sg + a[i]))
            return -1,count+delta
        else:
            delta = abs(1 - (sg + a[i]))
            return 1,count+delta


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

print(dp(n-1)[1])

Submission status: Runtime Error

Solution code:
N = int(input())

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


B = [A[0],(-1)*(A[0])//abs(A[0])]
ANS = []
#print(b)
for i in range(len(B)):
    b = B[i]
    ans = 0
    if i==1: ans = abs(b)+1
    for a in A[1:]:
        #print("a+b"+str(a+b))
        if a+b==0:
            ans += 1
            b = (-1)*(b)//abs(b)
        elif b*(a+b)<0:
            b += a
        else:
            ans += abs(a+b)+1
            #print("ans"+str(ans))
            b = (-1)*(a+b)//abs(a+b)
        #print(b)
    ANS.append(ans)
print(min(ANS))

Submission status: Runtime Error

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
    
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: Runtime Error

Solution code:
n = int(input())
a = list(map(int, input().split()))
s = a[0]
ans = 0
for i in range(1, n):
    ans +=  abs(s + a[i]) + 1 if s * (s + a[i]) >= 0 else 0
    s = -1 * s // abs(s) if s * (s + a[i]) >= 0 else s + a[i]

print(ans)

Submission status: Runtime Error

Solution code:
N,T =map(int,input().split())
t = map(int,input().split())
amount =0


    
for index in range(N-1):
    t_sub = t[index+1]-t[index]
    amount+=min(t_sub,T)

        
amount +=T

print(amount)

Submission status: Runtime Error

Solution code:
import sys,time
X, Y = map(int,input().split())
time.sleep((X%7)/5)

Submission status: Runtime Error

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 += math.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: Runtime Error

Solution code:
N = int( input() )
A = list( map( int, input().split() ) )
ans = 0
s = A[ 0 ]
for i in range( 1, N, 1 ):
  ns = s + A[ i ]
  if ns * s >= 0:
    ns = s // abs( s ) * -1
    ans += abs( ns - ( s + A[ i ] ) )
  s = ns
print( ans )