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 sys
n = int(input())
a_ls = [int(i) for i in sys.stdin.readline().split()]

INF = 10**18
best = INF
for i in range(2):
    flg = i % 2
    _sum = 0
    cnt = 0
    for a in a_ls:
        _sum += a
        if flg:
           if _sum <= 0:
               cnt += 1 - _sum
               _sum = 1
        else:
            if _sum >= 0:
                cnt += _sum + 1
                _sum = -1
        flg = 1 if flg == 0 else 0
    best = min(best, cnt)
print(best)

Submission status: Accepted

Solution code:
N = int(input())
a = list(map(int,input().split()))
ans1 = 0
ans2 = 0
S1 = 0
S2 = 0
for n in range(N):
    S1 += a[n]
    S2 += a[n]
    if n%2 == 0:
        if S1 >= -1:
            ans1 += S1 + 1
            S1 = -1
        if S2 <= 1:
            ans2 += 1 - S2
            S2 = 1
    if n%2 == 1:
        if S1 <= 1:
            ans1 += 1 - S1
            S1 = 1
        if S2 >= -1:
            ans2 += S2 + 1
            S2 = -1
print(min(ans1,ans2))

Submission status: Accepted

Solution code:
n = int(input())
alist = list(map(int, input().split()))
acounter = 0
bcounter = 0
num = 0
for i in range(n):
    num += alist[i]
    if i % 2 == 0:
        if num <= 0:
            acounter += abs(num) + 1
            num = 1
    else:
        if num >= 0:
            acounter += num + 1
            num = -1

num = 0
for i in range(n):
    num += alist[i]
    if i % 2 != 0:
        if num <= 0:
            bcounter += abs(num) + 1
            num = 1
    else:
        if num >= 0:
            bcounter += num + 1
            num = -1

print(min(acounter, bcounter))

Submission status: Accepted

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

tmp=0
tmp2=0
for i in range(n):
  tmp+=a[i]
  if i %2==0:
    if tmp>=0:
      tmp2+=abs(tmp)+1
      tmp=-1
  else:
    if tmp<=0:
      tmp2+=abs(tmp)+1
      tmp=1
print(min(ans,tmp2))

Submission status: Accepted

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

s = [0]
for i in range(n):
    s.append(s[-1] + a[i])
s = s[1:]

# 0th: positive
ans1 = 0
c = [0]
for i in range(n):
    if i % 2 == 0:
        _b = max(1 - s[i] - c[-1], 0)
    else:
        _b = min(-1 - s[i] - c[-1], 0)
    c.append(c[-1] + _b)
    ans1 += abs(_b)

# 0th: negatie
ans2 = 0
c = [0]
for i in range(n):
    if i % 2 != 0:
        _b = max(1 - s[i] - c[-1], 0)
    else:
        _b = min(-1 - s[i] - c[-1], 0)
    c.append(c[-1] + _b)
    ans2 += abs(_b)

print(min(ans1, ans2))

Submission status: Accepted

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')

def main():
    N=I()
    A=LI()
    def solve(is_minus):
        now = 0
        res = 0
        for a in A:
            now += a
            if is_minus:#累積和が負でないといけない
                if now >= 0:#負じゃない
                    res += abs(now-(-1))
                    now = -1
            else:#累積和が負でないといけない
                if now <= 0:#負じゃない
                    res += abs(now-1)
                    now = 1
            is_minus ^= 1 #true/falseを反転
        return res

    ans = min(solve(True), solve(False)) ##ポケットモンスター 奇数から始める/偶数から始める
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    A = [int(i) for i in input().split()]
    ans1 = 0
    S1 = [0] * N
    S1[0] = A[0]
    if A[0] == 0:
        S1[0] = -1
        ans1 += 1
    for i in range(1, N):
        S1[i] = S1[i-1] + A[i]
        if S1[i]*S1[i-1] < 0:
            continue
        if S1[i-1] > 0:
            S1[i] = -1
            ans1 += abs((-1) - (S1[i-1]+A[i]))
        else:
            S1[i] = 1
            ans1 += abs(1 - (S1[i-1]+A[i]))
    S2 = [0] * N
    ans2 = 0
    if A[0] > 0:
        S2[0] = -1
        ans2 += abs((-1) - A[0])
    else:
        S2[0] = 1
        ans2 += abs(1 - A[0])
    for i in range(1, N):
        S2[i] = S2[i-1] + A[i]
        if S2[i]*S2[i-1] < 0:
            continue
        if S2[i-1] > 0:
            S2[i] = -1
            ans2 += abs((-1) - (S2[i-1]+A[i]))
        else:
            S2[i] = 1
            ans2 += abs(1 - (S2[i-1]+A[i]))

    print(min(ans1, ans2))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
#Binary Indexed Tree (1-index！！！！！！！！)
class BinaryIndexedTree():
    def __init__(self, size):
        self.__node=[0]*(size+1)
        self.size = size

    #node[index]にvalueを足して、BITを更新
    def add(self, index, value):
        while index <= self.size:
            self.__node[index] += value
            index += index&-index    
    
    #indexまでの和を返す
    def sum(self, index):
        ret = 0 #零元・単位元
        while index > 0:
            ret += self.__node[index]
            index -= index&-index    
        return ret

    def update_max(self, index, value):
        while index <= self.size:
            self.__node[index] = max(self.__node[index], value)
            index += index & -index


    #indexまでの最大値を返す
    def query_max(self, index):
        ret = 0
        while index > 0:
            ret = max(ret, self.__node[index])
            index -= index & -index
        return ret
        
        

    #0-indexでの添字を受け取って、1-indexでの添字での値を返す
    def get_node(self, index):
        return self.__node[index]
def main():
    N=I()
    A=LI()
    def solve(is_minus):
        B=BinaryIndexedTree(N)
        # print(is_minus)
        for i,a in enumerate(A,start=1):
            B.add(i,a)
        res = 0
        for i in range(1,N+1):
            s = B.sum(i)
            # print("sum",B.sum(i),"is_minus",is_minus)
            if is_minus:
                if s>=0:
                    res += abs(s-(-1))
                    B.add(i,(-1-s))
            else:
                if s<=0:
                    res += abs(s-1)
                    B.add(i,abs(s-1))
            # print(res)
            is_minus ^= 1
        return res

    ans = min(solve(True), solve(False))
    print(ans)
    # *cumsum, = accumulate(A)
    # print(cumsum)/
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
A = list(map(int, input().split()))
 
#偶数項を正とする場合
even_ans = 0
tot = 0
 
for i in range(n):
    tot += A[i]
    #偶数項では累積和を正とする
    if i % 2 == 1:
        if tot > 0:
            pass
        else:
            even_ans += abs(1 - tot)
            tot = 1
    #奇数項では累積和を負とする
    else:
        if tot < 0:
            pass
        else:
            even_ans += abs(-1-tot)
            tot = -1
 
#奇数項を正とする場合
odd_ans = 0
tot = 0
 
for i in range(n):
    tot += A[i]
    #偶数項では累積和を正とする
    if i % 2 == 1:
        if tot < 0:
            pass
        else:
            odd_ans += abs(-1 - tot)
            tot = -1
    #奇数項では累積和を負とする
    else:
        if tot > 0:
            pass
        else:
            odd_ans += abs(1-tot)
            tot = 1
 
ans = min(even_ans, odd_ans)
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
ans=10**19

for i in [-1,1]:
    b=0
    c=0
    for j in a:
        b+=j
        if b*i<=0:
            c+=abs(b-i)
            b=i
        i*=-1
    ans=min(ans,c)

print(ans)

Submission status: Accepted

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

#偶数項を正とする場合
even_ans = 0
tot = 0

for i in range(n):
    tot += A[i]
    #偶数項では累積和を正とする
    if i % 2 == 1:
        if tot > 0:
            pass
        else:
            even_ans += abs(1 - tot)
            tot = 1
    #奇数項では累積和を負とする
    else:
        if tot < 0:
            pass
        else:
            even_ans += abs(-1-tot)
            tot = -1

#奇数項を正とする場合
odd_ans = 0
tot = 0

for i in range(n):
    tot += A[i]
    #偶数項では累積和を正とする
    if i % 2 == 1:
        if tot < 0:
            pass
        else:
            odd_ans += abs(-1 - tot)
            tot = -1
    #奇数項では累積和を負とする
    else:
        if tot > 0:
            pass
        else:
            odd_ans += abs(1-tot)
            tot = 1

ans = min(even_ans, odd_ans)
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
l=list(map(int,input().split()))
count1=0
count2=0
sum1,sum2=0,0
now=1#一致させたい符号
for i in range(n):#第一項は正の時
  sum1+=l[i]
  if sum1*now>0:
    pass
  else:
    count1+=abs(now-sum1)
    sum1=now
  now*=-1
now=-1
for i in range(n):#第一項はhuの時
  sum2+=l[i]
  if sum2*now>0:
    pass
  else:
    count2+=abs(now-sum2)
    sum2=now
  now*=-1
print(min(count1,count2))

Submission status: Accepted

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

def seq(a,t):
    ans = 0
    x = 0
    for i in a:
        x+=i
        if t==True and x<1:
            ans+=1-x
            x=1
        elif t==False and x>-1:
            ans+=x+1
            x=-1
        t = not t
    return ans
print(min(seq(A,True),seq(A,False)))

Submission status: Accepted

Solution code:
n = int(input())
A = [int(a) for a in input().split()]

ans = 0
s = A[0]

if s <= 0:
    ans -= s-1
    s = 1
for i in range(1, n):
    if s > 0:
        s += A[i]
        if s >= 0:
            ans += s+1
            s = -1
    elif s < 0:
        s += A[i]
        if s <= 0:
            ans -= s-1
            s = 1

s = A[0]
c = 0
if s >= 0:
    c += s+1
    s = -1
for i in range(1, n):
    if s > 0:
        s += A[i]
        if s >= 0:
            c += s+1
            s = -1
    elif s < 0:
        s += A[i]
        if s <= 0:
            c -= s-1
            s = 1
ans = min(ans, c)
print(ans)

Submission status: Accepted

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

def f(toggle):
	global a, n
	s = 0
	res = 0
	for i in range(n):
		s += a[i]
		if toggle == 1 and s < 1:
			res += -s + 1
			s = 1
		elif toggle == 0 and s > -1:
			res += s + 1
			s = -1

		toggle = not toggle

	return res

print(min(f(1), f(0)))

Submission status: Accepted

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

s = 0
c1 = 0
for i in range(N):
    s += A[i]
    if i % 2:
        ns = min(s, -1)
        c1 += s - ns
        s += ns - s
    else:
        ns = max(s, 1)
        c1 += ns - s
        s += ns - s

s = 0
c2 = 0
for i in range(N):
    s += A[i]
    if i % 2:
        ns = max(s, 1)
        c2 += ns - s
        s += ns - s
    else:
        ns = min(s, -1)
        c2 += s - ns
        s += ns - s

print(min(c1, c2))

Submission status: Accepted

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

sa=[0]*N
sa[0]=A[0]
for i in range(1,N):
  sa[i]=sa[i-1]+A[i]
  
pm=1
ans=0
d=0
for i in range(N):
  if sa[i]+d!=pm*abs(sa[i]+d) or sa[i]+d==0:
    ans+=abs(pm-sa[i]-d)
    d+=pm-sa[i]-d
  pm*=-1
  
pm=-1
ans2=0
d=0
for i in range(N):
  if sa[i]+d!=pm*abs(sa[i]+d) or sa[i]+d==0:
    ans2+=abs(pm-sa[i]-d)
    d+=pm-sa[i]-d
  pm*=-1

print(min(ans,ans2))

Submission status: Accepted

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

def f(a, sgn):
    cnt = 0
    s = 0
    for i in range(n):
        s += a[i]
        sgn *= (-1) #判定する符号は交互に変わる
        if s * sgn <= 0: #sgn一致しなければその積は負
            x = s + sgn*(-1)
            s -= x
            cnt += abs(x)
        
    return cnt
ans = min(f(a, 1), f(a, -1))
print(ans)

Submission status: Accepted

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

answers = []
for l in range(2):
  sum = 0
  answer = 0
  for i in range(n):
    sum += a[i]
    if (i + l) % 2 == 0:
      if sum >= 0:
        answer += abs(sum) + 1
        sum = -1
    else:
      if sum <= 0:
        answer += abs(sum) + 1
        sum = 1
  answers.append(answer)

print(min(answers))

Submission status: Accepted

Solution code:
from itertools import accumulate
import copy

def sol(acmA, sign=1):    
  add = 0
  ans = 0
  if sign==1:
    if acmA[0] <= 0:
      add = -acmA[0]+1
      ans = abs(-acmA[0]+1)
      acmA[0] = 1
  else:  
    if acmA[0] >= 0:
      add = -acmA[0]-1
      ans = abs(-acmA[0]-1)
      acmA[0] = -1      
      
  for i in range(1,N):
    acmA[i] += add
    tmp_add = 0
    if sign == 1:
      if i%2==0:
        if acmA[i] <=0:
          tmp_add = -acmA[i]+1
      else:
        if acmA[i] >=0:
          tmp_add = -acmA[i]-1
    else:
      if i%2==1:
        if acmA[i] <=0:
          tmp_add = -acmA[i]+1
      else:
        if acmA[i] >=0:
          tmp_add = -acmA[i]-1     
   
    #print(i, tmp_add, acmA[i])
    acmA[i] += tmp_add
    add +=  tmp_add
    ans +=abs(tmp_add)
  if acmA[-1] == 0: return ans +1
  else: return ans

N = int(input())
A = list(map(int,input().split()))
acmA = list(accumulate(A))
acmA2 = copy.deepcopy(acmA)
print(min(sol(acmA, 1), sol(acmA2, -1)))

Submission status: Accepted

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

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

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

print(min(res1,res2))

Submission status: Accepted

Solution code:
def examC():
    N = I()
    a = LI()
    ansC = []
    """
        if a[0]<0:
        for i in range(N):
            a[i] = -a[i]
    """
    for l in range(2):
        sumA = 0
        ans = 0
        for i in range(N):
            sumA += a[i]
            if (i + l) % 2 == 0:
                if sumA >= 0:
                    ans += abs(sumA)+1
                    sumA = -1
            else:
                if sumA <= 0:
                    ans += abs(sumA)+1
                    sumA = 1
        ansC.append(ans)
    print(min(ansC))

import sys
import copy
import bisect
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

examC()

Submission status: Accepted

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

sum = 0
ans1 = 0

for i in range(n):
    sum += a[i]
    if i % 2 == 0:
        if sum == 0:
            sum = 1
            ans1 +=1
        elif sum > 0:
            pass
        else:
            ans1 += 1 - sum  
            sum = 1
    else:
        if sum == 0:
            ans1 += 1
            sum = -1
        elif sum < 0:
            pass
        else:
            ans1 += 1 + sum
            sum = -1

sum = 0
ans2 = 0
# 奇数項までの和が正、偶数項が負とした場合
for i in range(n):
    sum += a[i]
    if i % 2 == 1:
        if sum == 0:
            ans2 +=1
            sum = 1
        elif sum > 0:
            pass
        else:
            ans2 += 1 - sum
            sum = 1       
    else:
        if sum == 0:
            sum = -1
            ans2 += 1
        elif sum < 0:
            pass
        else:
            ans2 += 1 + sum
            sum = -1


print(min(ans1, ans2))

Submission status: Accepted

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

def chk(a_list, sgn):
  
  cum_n = 0
  count = 0
  
  for a in a_list:
    cum_n += a
    
    if sgn>0 and cum_n<=0:
      count += abs(cum_n-1)
      cum_n = 1
    elif sgn<0 and cum_n>=0:
      count += abs(cum_n-(-1))
      cum_n = -1
      
    sgn = sgn*(-1)
  
  return(count)

print(min(chk(A, 1), chk(A, -1)))

Submission status: Accepted

Solution code:
import copy
n = int(input())
a = [int(i) for i in input().split()]
b=a.copy()
s0p = a[0]
s0n = b[0]
countp = 0
countn = 0

if a.count(0)==n:
  print(2*n-1)
  exit()

if s0p<=0:
  s0p+=(abs(a[0])+1)
  countp+=(abs(a[0])+1)
  
if s0n>=0:
  s0n-=(abs(b[0])+1)
  countn+=(abs(b[0])+1)

for i in range(1,n):
  s1 = s0p+a[i]
  if s0p*s1>=0:
    if s1>0:
      a[i]-=(abs(s1)+1)
      countp+=(abs(s1)+1)
    elif s1<0:
      a[i]+=(abs(s1)+1)
      countp+=(abs(s1)+1)
    elif s1==0:
      if s0p>0:
        a[i]-=1
        countp+=1
      elif s0p<0:
        a[i]+=1
        countp+=1
  s0p += a[i]

for i in range(1,n):
  s1 = s0n+b[i]
  if s0n*s1>=0:
    if s1>0:
      b[i]-=(abs(s1)+1)
      countn+=(abs(s1)+1)
    elif s1<0:
      b[i]+=(abs(s1)+1)
      countn+=(abs(s1)+1)
    elif s1==0:
      if s0n>0:
        b[i]-=1
        countn+=1
      elif s0n<0:
        b[i]+=1
        countn+=1
  s0n += b[i]
  
print(countp if countp<=countn else(countn))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, A):
    S = [A[0]]
    for a in A[1:]:
        S.append(S[-1]+a)

    def f(sig):
        o = 0
        ans = 0
        for s in S:
            s += o
            if s == 0:
                ans += 1
                o -= sig
            elif sig * s > 0:
                ans += abs(s) + 1
                o -= sig*(abs(s) + 1)
            sig *= -1
        return ans
            
    return min(f(1), f(-1))


def main():
    N = read_int()
    A = read_int_n()
    print(slv(N, A))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

def calc_tmp_ans(tmp_ans, cum_sum):
    for i in range(1, N):
        #print(i, tmp_ans)
        prev_cum_sum = cum_sum
        cum_sum += a[i]
        if cum_sum * prev_cum_sum >= 0:
            tmp_ans += abs(cum_sum) + 1
            if prev_cum_sum > 0:
                cum_sum = -1
            else:
                cum_sum = 1
    return tmp_ans

ans = 1000000000000000
if a[0] == 0:
    ans = min(ans, calc_tmp_ans(1, 1))
    ans = min(ans, calc_tmp_ans(1, -1))
else:
    ans = min(ans, calc_tmp_ans(0, a[0]))
    if a[0] > 0:
        ans = min(ans, calc_tmp_ans(a[0] + 1, -1))
    else:
        ans = min(ans, calc_tmp_ans(abs(a[0]) + 1, 1))
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split())) 
# -+-+-
cost1 = 0
sum1 = 0
for i in range(N):
    sum1 += A[i]
    if (i + 1) % 2 == 0 and sum1 <= 0:
        cost1 += (abs(sum1) + 1)
        sum1 = 1
    if (i + 1) % 2 != 0 and sum1 >= 0:
        cost1 += (abs(sum1) + 1)
        sum1 = -1

# +-+-+
cost2 = 0
sum2 = 0
for i in range(N):
    sum2 += A[i]
    if (i + 1) % 2 == 0 and sum2 >= 0:
        cost2 += (abs(sum2) + 1)
        sum2 = -1
    if (i + 1) % 2 != 0 and sum2 <= 0:
        cost2 += (abs(sum2) + 1)
        sum2 = 1

print(min(cost1, cost2))

Submission status: Accepted

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

wa=0
ans1=0
for i in range(n):
    wa+=a[i]
    if i%2==0:
        if wa==0:
            wa=1
            ans1+=1
        elif wa>0:
            pass
        else:
            ans1+=1-wa
            wa=1
    else:
        if wa==0:
            wa=-1
            ans1+=1
        elif wa<0:
            pass
        else:
            ans1+=wa+1
            wa=-1
wa=0
ans2=0
for i in range(n):
    wa+=a[i]
    if i%2:
        if wa==0:
            wa=1
            ans2+=1
        elif wa>0:
            pass
        else:
            ans2+=1-wa
            wa=1
    else:
        if wa==0:
            wa=-1
            ans2+=1
        elif wa<0:
            pass
        else:
            ans2+=wa+1
            wa=-1

print(min(ans1,ans2))

Submission status: Accepted

Solution code:
n = input()
a = [int(i) for i in input().split()]
def chk(a, t):
  ans = 0
  x = 0
  for i in a:
    x += i
    if t == True and x < 1:
      ans+=1-x
      x=1
    elif t == False and x>-1:
      ans+=x+1
      x=-1
    t=not t
  return ans
print(min(chk(a,True),chk(a,False)))

Submission status: Accepted

Solution code:
def f(n, a, p, r):
    for i in range(1, n):
        t = p + a[i]
        if p < 0 and t <= 0:
            r += 1 - t
            t = 1
        elif p > 0 and t >= 0:
            r += t + 1
            t = -1
        p = t
    return r


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

# 最初がプラス
p = a[0]
r = 0
if p <= 0:
    r += 1 - p
    p = 1
result1 = f(n, a, p, r)

# 最初がマイナス
p = a[0]
r = 0
if p >= 0:
    r += p + 1
    p = -1
result2 = f(n, a, p, r)

print(min(result1, result2))

Submission status: Accepted

Solution code:
n = int(input())
a = [int(a) for a in input().split()]

def f(times, prefix_sum):
    for i in range(1, n):
        if prefix_sum < 0:
            if prefix_sum + a[i] > 0:
                prefix_sum += a[i]
            else:
                times += 1 - (prefix_sum + a[i])
                prefix_sum = 1      
        elif prefix_sum > 0:
            if prefix_sum + a[i] < 0:
                prefix_sum += a[i]
            else:
                times += abs(-1 - (prefix_sum + a[i]))
                prefix_sum = -1
    
    return times

if a[0] > 0:
    t1 = 0
    p1 = a[0]
else:
    t1 = 1 - a[0]
    p1 = 1


if a[0] < 0:
    t2 = 0
    p2 = a[0]
else:
    t2 = abs(-1 - a[0])
    p2 = -1
    

print(min(f(t1, p1), f(t2, p2)))

Submission status: Accepted

Solution code:
input()
seq = list(map(int, input().rstrip("\n").split()))

iter_ = iter(seq)
ans1 = 0
for i, num in enumerate(iter_):
    if i == 0:
        sum_ = num
        if sum_ > 0:
            pass
        else:
            ans1 += abs(sum_ - 1)
            sum_ = 1
    else:
        sum_ += num
        if i % 2:
            if sum_ < 0:
                pass
            else:
                ans1 += abs(sum_ + 1)
                sum_ = -1
        else:
            if sum_ > 0:
                pass
            else:
                ans1 += abs(sum_ - 1)
                sum_ = 1

iter_ = iter(seq)
ans2 = 0
for i, num in enumerate(iter_):
    if i == 0:
        sum_ = num
        if sum_ < 0:
            pass
        else:
            ans2 += abs(sum_ + 1)
            sum_ = -1
    else:
        sum_ += num
        if i % 2:
            if sum_ > 0:
                pass
            else:
                ans2 += abs(sum_ - 1)
                sum_ = 1
        else:
            if sum_ < 0:
                pass
            else:
                ans2 += abs(sum_ + 1)
                sum_ = -1

print(min(ans1, ans2))

Submission status: Accepted

Solution code:
def z(s,l):
	for i in range(n-1):
		r=l+a[i+1]
		if r*l>=0:
			if l<=0:
				s+=1-r
				r=1
			else:
				s+=1+r
				r=-1
		l=r
	return s
n=int(input())
a=list(map(int,input().split()))
s1=0
l1=a[0]
if a[0]<=0:
	s1=1-a[0]
	l1=1
s2=0
l2=a[0]
if a[0]>=0:
	s2=a[0]+1
	l2=-1
print(min(z(s1,l1),z(s2,l2)))

Submission status: Accepted

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

# +, -, +, -, ...
sum = 0
count = 0
for i in range(n):
    sum += a[i]
    if i % 2 == 0:
        if sum <= 0:
            count += abs(sum) + 1
            sum = 1
    else:
        if sum >= 0:
            count += abs(sum) + 1
            sum = -1

# -, +, -, +, ...
sum2 = 0
count2 = 0
for i in range(n):
    sum2 += a[i]
    if i % 2 == 0:
        if sum2 >= 0:
            count2 += abs(sum2) + 1
            sum2 = -1
    else:
        if sum2 <= 0:
            count2 += abs(sum2) + 1
            sum2 = 1

print(min(count, count2))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
import itertools

def solve(n: int, a: "List[int]"):
    a_sum = list(itertools.accumulate(a))
    ## 一個目をマイナスにするバージョン
    dif1 = 0
    answer1 = 0
    for i in range(0,n):
        if i%2==0:
            if a_sum[i]+dif1>-1:
                answer1 += abs(-1-(a_sum[i]+dif1))
                dif1 += -1-(a_sum[i]+dif1)
        else:
            if a_sum[i]+dif1 <1:
                answer1 += abs(1-(a_sum[i]+dif1))
                dif1 += 1-(a_sum[i]+dif1)

    ## 一個目をプラスにするバージョン
    dif2 = 0
    answer2 = 0
    for i in range(0,n):
        if i%2==0:
            if a_sum[i]+dif2<1:
                answer2 += abs(1-(a_sum[i]+dif2))
                dif2 += 1-(a_sum[i]+dif2)
        else:
            if a_sum[i]+dif2>-1:
                answer2 += abs(-1-(a_sum[i]+dif2))
                dif2 += -1-(a_sum[i]+dif2)
        
    print(min(answer1,answer2))
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    n = int(next(tokens))  # type: int
    a = [int(next(tokens)) for _ in range(n)]  # type: "List[int]"
    solve(n, a)

if __name__ == '__main__':
    main()

Submission status: Accepted

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


def chk(a, positive):
    ans = tmp = 0
    for x in a:
        tmp += x
        if positive and tmp < 1:
            ans += 1-tmp
            tmp = 1
        elif not positive and tmp > -1:
            ans += abs(-1-tmp)
            tmp = -1

        positive = not positive
    return ans

print(min((chk(a, True), chk(a, False))))

Submission status: Accepted

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

ans_plus=0
tmp=0
if a[0]<=0:
    ans_plus=1-a[0]
    tmp=1
else:
    tmp=a[0]
plus_flag=False
for i in a[1:]:
    tmp+=i
    if plus_flag==True and tmp>0:
        pass
    elif plus_flag==True and tmp<=0:
        ans_plus+=1-tmp
        tmp=1
    elif plus_flag==False and tmp<0:
        pass
    elif plus_flag==False and tmp>=0:
        ans_plus+=1+tmp
        tmp=-1
    plus_flag=not plus_flag
#print(ans_plus)

ans_minus=0
tmp=0
if a[0]>=0:
    ans_minus=1+a[0]
    tmp=-1
else:
    tmp=a[0]
plus_flag=True
for i in a[1:]:
    tmp+=i
    if plus_flag==True and tmp>0:
        pass
    elif plus_flag==True and tmp<=0:
        ans_minus+=1-tmp
        tmp=1
    elif plus_flag==False and tmp<0:
        pass
    elif plus_flag==False and tmp>=0:
        ans_minus+=1+tmp
        tmp=-1
    plus_flag=not plus_flag
#print(ans_minus)
print(min(ans_plus, ans_minus))

Submission status: Accepted

Solution code:
def f(flg, an):
    accum = 0
    ret = 0
    for ai in an:
        accum += ai
        if flg:
            flg = False
            if accum <= 0:
                ret += -accum + 1
                accum = 1
        else:
            flg = True
            if 0 <= accum:
                ret += accum + 1
                accum = -1
    return ret


def main():
    an = list(map(int, open(0).read().split()[1:]))
    print(min(f(False, an), f(True, an)))
    return


main()