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:
def solve(f, A):
    r, s = 0, 0
    for a in A:
        s += a
        if s == 0:
            r += 1
            s = f
        elif s * f < 0:
            r += -(s * f) + 1
            s = f
        f = -f
    return r

def main():
    N = int(input())
    A = list(map(int, input().split()))
    return min(solve(1, A), solve(-1, A))

print(main())

Submission status: Accepted

Solution code:
# coding: utf-8
# hello worldと表示する
import sys
import numpy
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
from copy import deepcopy
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

n=I()
seq=LI()
'''if seq[0]>0:
    pm=-1
    sm=seq[0]
    count=0
    for i in range(n-1):
        sm=sm+seq[i+1]
        if pm>0:
            if sm<=0:
                count+=1-sm
                sm=1
            pm=-1
        else:
            if sm>=0:
                count+=1+sm
                sm=-1
            pm=1
    print(count)
elif seq[0]<0:
    pm=1
    sm=seq[0]
    count=0
    for i in range(n-1):
        sm=sm+seq[i+1]
        if pm>0:
            if sm<=0:
                count+=1-sm
                sm=1
            pm=-1
        else:
            if sm>=0:
                count+=1+sm
                sm=-1
            pm=1
    print(count)'''
if seq[0]>0:
    pm=-1
    sm=seq[0]
    count=0
    for i in range(n-1):
        sm=sm+seq[i+1]
        if pm>0:
            if sm<=0:
                count+=1-sm
                sm=1
            pm=-1
        else:
            if sm>=0:
                count+=1+sm
                sm=-1
            pm=1
    count1=count
    pm=1
    sm=-1
    count=1+seq[0]
    for i in range(n-1):
        sm=sm+seq[i+1]
        if pm>0:
            if sm<=0:
                count+=1-sm
                sm=1
            pm=-1
        else:
            if sm>=0:
                count+=1+sm
                sm=-1
            pm=1
    count2=count
    print(min(count1,count2))
elif seq[0]<0:
    pm=1
    sm=seq[0]
    count=0
    for i in range(n-1):
        sm=sm+seq[i+1]
        if pm>0:
            if sm<=0:
                count+=1-sm
                sm=1
            pm=-1
        else:
            if sm>=0:
                count+=1+sm
                sm=-1
            pm=1
    count1=count
    pm=-1
    sm=1
    count=1-seq[0]
    for i in range(n-1):
        sm=sm+seq[i+1]
        if pm>0:
            if sm<=0:
                count+=1-sm
                sm=1
            pm=-1
        else:
            if sm>=0:
                count+=1+sm
                sm=-1
            pm=1
    count2=count
    print(min(count1,count2))
else:
    pm=-1
    sm=1
    count=1
    for i in range(n-1):
        sm=sm+seq[i+1]
        if pm>0:
            if sm<=0:
                count+=1-sm
                sm=1
            pm=-1
        else:
            if sm>=0:
                count+=1+sm
                sm=-1
            pm=1
    count1=count
    pm=1
    sm=-1
    count=1
    for i in range(n-1):
        sm=sm+seq[i+1]
        if pm>0:
            if sm<=0:
                count+=1-sm
                sm=1
            pm=-1
        else:
            if sm>=0:
                count+=1+sm
                sm=-1
            pm=1
    count2=count
    print(min(count1,count2))

Submission status: Accepted

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

    res = 0
    sums = []

    for i in range(n):
        if i == 0:
            sums.append(A[i])
            if A[i] == 0:
                sums[i] = 1
                res += 1
            elif A[i] < 0:
                res += 1 - A[i]
                sums[i] = 1
        else:
            sums.append(sums[i-1] + A[i])
            if sums[i] == 0:
                if sums[i-1] > 0:
                    sums[i] = -1
                    res += 1
                else:
                    sums[i] = 1
                    res += 1
            elif (sums[i-1] > 0) and (sums[i] > 0):
                res += 1 + sums[i]
                sums[i] = -1
            elif (sums[i-1] < 0) and (sums[i] < 0):
                res += 1 - sums[i]
                sums[i] = 1
    
    sums = []
    res1 = 0

    for i in range(n):
        if i == 0:
            sums.append(A[i])
            if A[i] == 0:
                sums[i] = -1
                res1 += 1
            elif A[i] > 0:
                res1 += 1 + A[i]
                sums[i] = -1
        else:
            sums.append(sums[i-1] + A[i])
            if sums[i] == 0:
                if sums[i-1] > 0:
                    sums[i] = -1
                    res1 += 1
                else:
                    sums[i] = 1
                    res1 += 1
            elif (sums[i-1] > 0) and (sums[i] > 0):
                res1 += 1 + sums[i]
                sums[i] = -1
            elif (sums[i-1] < 0) and (sums[i] < 0):
                res1 += 1 - sums[i]
                sums[i] = 1
    
    print(min(res, res1))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:

N=int(input())
A=list(map(int, input().split()))
#和の符号が異なる


ans1=0
ans2=0

if A[0]==0:
    a0_1=1
    a0_2=-1
    ans1+=1
    ans2+=1
elif A[0]>1:
    a0_1=A[0]
    a0_2=-1
    ans2+=A[0]+1
else:
    a0_1=1
    a0_2=A[0]
    ans1+=1-A[0]


now1=a0_1
for i in range(1,N):
    if now1*(now1+A[i])<0:
        now1+=A[i]
    else:
        if now1>0:
            add=(-1)*(now1+1)
        else:
            add=(-1)*(now1-1)
        now1+=add
        ans1+=abs(add-A[i])
    #print(now1)

now2=a0_2
for i in range(1,N):
    if now2*(now2+A[i])<0:
        now2+=A[i]
    else:
        if now2>0:
            add=(-1)*(now2+1)
        else:
            add=(-1)*(now2-1)
        now2+=add
        ans2+=abs(add-A[i])
ans=min(ans1, ans2)
print(ans)
#print(ans1, ans2)

Submission status: Accepted

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

def f(isPosi):
    total = 0
    cnt = 0
    for i in a:
        total += i
        if isPosi:
            if total >= 0:
                cnt += 1 + total
                total = -1
            isPosi = False
        else:
            if total <= 0:
                cnt += 1 - total
                total = 1
            isPosi = True
    return cnt

print(min(f(True), f(False)))

Submission status: Accepted

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


def cost(t):
    res = 0
    sum = 0
    for y in s:
        sum += y
        if sum * t <= 0:
            res += abs(sum - t)
            sum = t
        t *= -1
    return res


print(min(cost(1), cost(-1)))

Submission status: Accepted

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

B1 = [(-1)**i for i in range(n)]
B2 = [(-1)**(i+1) for i in range(n)]

def func(A, B):
    cum = 0
    res = 0
    for i in range(n):
        cum += A[i]
        if B[i] > 0 and cum <= 0:
            res += 1-cum
            cum = 1
        elif B[i] < 0 and cum >= 0:
            res += cum+1
            cum = -1
    return res
     
print(min(func(A, B1), func(A, B2)))

Submission status: Accepted

Solution code:
from functools import lru_cache
n = int(input())
s = list(map(int, input().split()))


@lru_cache(maxsize=None)
def cost_e():
    res = 0
    sum = 0
    for j, y in enumerate(s, 1):
        tmp = sum + y
        if j & 1 and tmp >= 0:
            sum = -1
            res += abs(tmp) + 1
        elif not j & 1 and tmp <= 0:
            sum = 1
            res += abs(tmp) + 1
        else:
            sum = tmp
    return res


@lru_cache(maxsize=None)
def cost_o():
    res = 0
    sum = 0
    for j, y in enumerate(s, 1):
        tmp = sum + y
        if j & 1 and tmp <= 0:
            sum = 1
            res += abs(tmp) + 1
        elif not j & 1 and tmp >= 0:
            sum = -1
            res += abs(tmp) + 1
        else:
            sum = tmp
    return res


print(min(cost_e(), cost_o()))

Submission status: Accepted

Solution code:
import math
#import sys
#input = sys.stdin.readline

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

def ValueToBits(x,digit):
    res = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        res[i]=now%2
        now = now >> 1
    return res

def BitsToValue(arr):
    n = len(arr)
    ans = 0
    for i in range(n):
        ans+= arr[i] * 2**i
    return ans

def ZipArray(a):
    aa = [[a[i],i]for i in range(n)]

    aa.sort(key = lambda x : x[0])
    for i in range(n):
        aa[i][0]=i+1
    aa.sort(key = lambda x : x[1])
    b=[aa[i][0] for i in range(len(a))]
    return b

def ValueToArray10(x, digit):
    ans = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        ans[digit-i-1] = now%10
        now = now //10
    return ans

def Zeros(a,b):
    if(b<=-1):
        return [0 for i in range(a)]
    else:
        return [[0 for i in range(b)] for i in range(a)]

def AddV2(v,w):
    return [v[0]+w[0],v[1]+w[1]]

dir4 = [[1,0],[0,1],[-1,0],[0,-1]]


def clamp(x,y,z):
    return max(y,min(z,x))

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
            
#
def Zaatsu(a):
    a.sort()
    now = a[0][0]
    od = 0
    for i in range(n):
        if(now==a[i][0]):
            a[i][0]=od
        else:
            now = a[i][0]
            od+=1
            a[i][0] = od
    
    a.sort(key = lambda x : x[1])
    return a

class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)

    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # 併合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)


'''
def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

p = 2
N = 10 ** 6 + 2
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

'''

def rl(x):
    return range(len(x))

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

#################################################
#################################################
#################################################
#################################################



#44-

n = int(input())

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

ans1 = 0
total = 0
for i in rl(a):
    if(i%2==0):
        if(total+a[i]<0):
            total = total+a[i]
        else:
            ans1 += total+a[i]+1
            total = -1
    else:
        if(total+a[i]>0):
            total = total+a[i]
        else:
            ans1 += -(total+a[i])+1
            total = 1

#print(ans1)

ans2 = 0
total = 0
for i in rl(a):
    if(i%2==1):
        if(total+a[i]<0):
            total = total+a[i]
        else:
            ans2 += total+a[i]+1
            total = -1
    else:
        if(total+a[i]>0):
            total = total+a[i]
        else:
            ans2 += -(total+a[i])+1
            total = 1

#print(ans2)

print(min(ans1,ans2))

Submission status: Accepted

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

sum1 = a_list[0]

def func(sum1):
    cost = 0
    for i in a_list[1:]:
        # 前の合計値と次の合計値の積が負になれば良い
        if sum1 * (sum1 + i) < 0:
            sum1 += i
            continue
        else:
            if sum1 < 0:
                a_new = 1 - sum1
                cost += a_new - i
                sum1 += a_new
            else:
                a_new = -1 - sum1
                cost += i - a_new
                sum1 += a_new

    return cost

if a_list[0] > 0:
    # リストの最初が-1の場合のコストも考える
    answer = min(func(sum1), func(-1)+a_list[0]+1)
elif a_list[0] < 0:
    answer = min(func(sum1), func(1)-a_list[0]+1)
else:
    # リストの最初が0だったとき
    answer = min(func(1), func(-1)) + 1

print(answer)

Submission status: Accepted

Solution code:
n = int(input())
pcount = 0
p = 0
mcount = 0
m = 0
a = list(map(int,input().split()))
if a[0] > 0:
    p = a[0]
    m = -1
    mcount = a[0] + 1
elif a[0] < 0:
    p = 1
    pcount = abs(a[0]) + 1
    m = a[0]
else:
    p = 1
    pcount = 1
    m = -1
    mcount = 1
for i in range(1,n):
    p += a[i]
    m += a[i]
    if i % 2 == 1:
        if p >= 0:
            pcount += p+1
            p = -1
        if m <= 0:
            mcount += abs(m) + 1
            m = 1
    else:
        if p <= 0:
            pcount += abs(p) + 1
            p = 1
        if m >= 0:
            mcount += m + 1
            m = -1
print(min(pcount,mcount))

Submission status: Accepted

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

#マイナススタート
now = 0
count = 0
for i,j in enumerate(a):
    now += j
    if i%2 == 0:
        if now >= 0:
            count += abs(now)+1
            now = -1
    else:
        if now <= 0:
            count += abs(now)+1
            now = 1

#プラススタート
now = 0
count2 = 0
for i,j in enumerate(a):
    now += j
    if i%2 == 0:
        if now <= 0:
            count2 += abs(now)+1
            now = 1
    else:
        if now >= 0:
            count2 += abs(now)+1
            now = -1

print(min(count,count2))

Submission status: Accepted

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

sm = a[0]


def f(sm):
    ret = 0
    for e in a[1:]:
        if sm * (sm + e) < 0:
            sm += e
            continue

        else:
            if sm > 0:
                a_mx = -sm - 1
                ret += e - a_mx
                sm += a_mx
            else:
                a_mn = -sm + 1
                ret += a_mn - e
                sm += a_mn

    return ret


if sm > 0:
    ans = min(f(sm), f(-1) + sm + 1)
elif sm < 0:
    ans = min(f(sm), f(1) - sm + 1)
else:
    ans = min(f(1), f(-1)) + 1

print(ans)

Submission status: Accepted

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


def check_1(a):
    
    ##正負正...
    res = 0
    s = 0
    for i in range(n):
        s += a[i]
        if i%2 == 0:
            if s <= 0:
                res += abs(s) + 1
                s = 1
        else:
            if s >= 0:
                res += abs(s) + 1
                s = -1
    return res

def check_2(a):
    ##負正負...
    res = 0
    s = 0
    for i in range(n):
        s += a[i]
        if i%2 == 0:
            if s >= 0:
                res += abs(s)+ 1
                s = -1
        else:
            if s <= 0:
                res += abs(s) + 1 
                s = 1
    return res

b = a[:]
print(min(check_1(a),check_2(b)))

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
m=0
curr=1
ans=0
for i in range(n):
  m+=a[i]
  if curr*m<=0:
    ans+=1-curr*m
    m=curr
  curr=-1*curr
ans2=0
m=0
curr=-1
for i in range(n):
  m+=a[i]
  if curr*m<=0:
    ans2+=1-curr*m
    m=curr
  curr=-1*curr
print(min(ans,ans2))

Submission status: Accepted

Solution code:

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


ans1 = 0
curr_sum = 0
next_sign = 1
for a in al:
    next_sum = curr_sum + a
    if next_sum >= 0 and next_sign == -1: 
        ans1 += next_sum+1
        next_sum = -1
    elif next_sum <= 0 and next_sign == 1:
        ans1 += (1-next_sum)
        next_sum = 1
    curr_sum = next_sum
    next_sign *= -1


ans2 = 0
curr_sum = 0
next_sign = -1
for a in al:
    next_sum = curr_sum + a
    if next_sum >= 0 and next_sign == -1: 
        ans2 += next_sum+1
        next_sum = -1
    elif next_sum <= 0 and next_sign == 1:
        ans2 += (1-next_sum)
        next_sum = 1
    curr_sum = next_sum
    next_sign *= -1

print(min(ans1,ans2))

Submission status: Accepted

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

count1 = 0
now = A[0]
if now <= 0:
  count1 += (1-A[0])
  now = 1
for i in range(1, N):
  if i%2 == 0:
    if now+A[i] <= 0:
      count1 += 1-(now+A[i])
      now = 1
    else:
      now += A[i]
  else:
    if now+A[i] >= 0:
      count1 += 1+(now+A[i])
      now = -1
    else:
      now += A[i]
      
count2 = 0
now = A[0]
if now >= 0:
  count2 += (1+A[0])
  now = -1
for i in range(1, N):
  if i%2 == 1:
    if now+A[i] <= 0:
      count2 += 1-(now+A[i])
      now = 1
    else:
      now += A[i]
  else:
    if now+A[i] >= 0:
      count2 += 1+(now+A[i])
      now = -1
    else:
      now += A[i]
      
print(min(count1, count2))

Submission status: Accepted

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

total = [0, 0]
ret = [0, 0]
for i in range(2):
    for j in range(n):
        total[i] += lst[j]
        if (i + j) % 2 == 0:
            if total[i] >= 0:
                ret[i] += total[i] + 1
                total[i] = -1
        else:
            if total[i] <= 0:
                ret[i] += abs(total[i] - 1)
                total[i] = 1

print(min(ret))

Submission status: Accepted

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

total = [0, 0]
ret = [0, 0]
for i in range(2):
    for j in range(n):
        total[i] += lst[j]
        if (i + j) % 2 == 0:
            if total[i] >= 0:
                ret[i] += abs(total[i] + 1)
                total[i] = -1
        else:
            if total[i] <= 0:
                ret[i] += abs(total[i] - 1)
                total[i] = 1

print(min(ret))

Submission status: Accepted

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

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
from collections import defaultdict
from collections import deque
from functools import lru_cache


#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)


#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1:
    arr.append([temp, 1])
  if arr==[]:
    arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n -1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n:
    return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############

N = I()
A = IL()

s = 0
count1 = 0
for i in range(N):
  s += A[i]
  if i%2:
    if s>-1:
      count1 += s+1
      s = -1
  else:
    if s<1:
      count1 += 1-s
      s = 1
      
s = 0
count2 = 0
for i in range(N):
  s += A[i]
  if i%2==0:
    if s>-1:
      count2 += s+1
      s = -1
  else:
    if s<1:
      count2 += 1-s
      s = 1
  
print(min(count1,count2))

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
l = len(a)
b = []
for i in range(l):
  b.append(a[i])
  
ans = 0
Ans = 0
summary = a[0]

if(summary == 0):
  summary = 1
  ans+= 1
  Summary = -1
  Ans+= 1
else:
  b[0] = int(-a[0]/ abs(a[0]))
  Ans+= abs(a[0]- b[0])
  Summary = b[0]  
  
for i in range(1, l):
  if(summary* (summary+ a[i])>= 0):
    if(summary > 0):
      ans+= a[i]+ summary+ 1
      a[i] = -summary- 1 
      summary= -1
    else:
      ans+= -summary+ 1- a[i]
      a[i] = -summary+ 1
      summary= 1
  else:
    summary+= a[i]

for i in range(1, l):
  if(Summary* (Summary+ b[i])>= 0):
    if(Summary > 0):
      Ans+= b[i]+ Summary+ 1
      b[i] = -Summary- 1 
      Summary= -1
    else:
      Ans+= -Summary+ 1- b[i]
      b[i] = -Summary+ 1
      Summary= 1
  else:
    Summary+= b[i]
    
print(min(ans, Ans))

Submission status: Accepted

Solution code:
import numpy as np

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

def to_minus_one(num):
    return -1 - num

def to_plus_one(num):
    return 1 - num

s_list = np.zeros(n)
s = 0
for i in range(n):
    s += a[i]
    s_list[i] += s


def cal(sum_list, t, ans):
    hoge = 0
    for i in range(n):
        sum_list[i] += hoge
        if (i+t) % 2 == 0:
            if sum_list[i] >= 0:
                hiku = to_minus_one(sum_list[i])
                hoge += hiku
                ans += abs(hiku)
            else:
                continue
        else:
            if sum_list[i] <= 0:
                tasu = to_plus_one(sum_list[i])
                hoge += tasu
                ans += abs(tasu)
    return ans

q = np.copy(s_list)
w = np.copy(s_list)
num1 = cal(q, 0, 0)
num2 = cal(w, 1, 0)

print(int(min(num1, num2)))

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
ans = [0, 0]
s = [0, 0]
for k in range(2):
  for i in range(n):
    t = (i + k) % 2 * 2 - 1
    s[k] += a[i]
    d = max(0, t * s[k] + 1)
    ans[k] += d
    s[k] += -t * d
print(min(ans))

Submission status: Accepted

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


def calc(val):
    # valには、１か−１を入れる。
    if (val * a[0] > 0):
        # 狙った符号のパターン
        temp = a[0]
        ans01 = 0

    else:
        # 違うパターン
        add = abs(a[0]) + 1
        ans01 = add
        temp = val

    for i in range(1, n):
        tar = temp + a[i]
        if (tar * temp < 0):
            temp = tar
        else:
            add = abs(tar) + 1
            ans01 += add
            if (temp > 0):
                temp = -1
            else:
                temp = 1

    return ans01


ans = min(calc(1), calc(-1))


print(ans)

Submission status: Accepted

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


# プラススタート ------------------
ans01 = 0
temp = a[0]
if (temp > 0):
    pass
else:
    add = abs(temp) + 1
    ans01 += add
    temp = 1

for i in range(1, n):
    tar = temp + a[i]
    if (tar * temp < 0):
        temp = tar
    else:
        add = abs(tar) + 1
        ans01 += add
        if (temp > 0):
            temp = -1
        else:
            temp = 1
    #print(tar, ans)
# マイナススタート ------------------
ans02 = 0
temp = a[0]
if (temp < 0):
    pass
else:
    add = abs(temp) + 1
    ans02 += add
    temp = -1

for i in range(1, n):
    tar = temp + a[i]
    if (tar * temp < 0):
        temp = tar
    else:
        add = abs(tar) + 1
        ans02 += add
        if (temp > 0):
            temp = -1
        else:
            temp = 1
    #print(tar, ans)

ans = min(ans01, ans02)

print(ans)

Submission status: Accepted

Solution code:
def calc(sign, A):
    cumsum_A = [0 for _ in range(len(A))]
    cumsum_A[0] = A[0]
    for i in range(len(cumsum_A) - 1):
        cumsum_A[i + 1] = cumsum_A[i] + A[i + 1]
    ret, offset = 0, 0
    for a in cumsum_A:
        b = a + offset
        if sign * b <= 0:
            diff = sign - b
            offset += diff
            ret += abs(diff)
        sign *= (-1)
    return ret


def main():
    N = int(input())
    A = list(map(int, input().split(' ')))
    print(min([calc(1, A), calc(-1, A)]))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
a = [int(i) for i in input().split()]
ans1 = 0
ans2 = 0
summ = 0
summ2 = 0
a2 = a[:]


for i in range(n):
    if i % 2 == 0:
        if summ + a[i] <= 0:
            ans1 += abs(summ + a[i]) + 1
            a[i] = -summ + 1
            summ = 1
        else:
            summ += a[i]
    else:
        if summ + a[i] >= 0:
            ans1 += abs(summ + a[i]) + 1
            a[i] = -summ -1
            summ = -1
        else:
            summ += a[i]
#-+-
for i in range(n):
    if i % 2 != 0:
        if summ2 + a2[i] <= 0:
            ans2 += abs(summ2 + a2[i]) + 1
            a2[i] = -summ2 + 1
            summ2 = 1
        else:
            summ2 += a2[i]
    else:
        if summ2 + a2[i] >= 0:
            ans2 += abs(summ2 + a2[i]) + 1
            a2[i] = -summ2 -1
            summ2 = -1
        else:
            summ2 += a2[i]


print(min(ans1, ans2))

Submission status: Accepted

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

t = 0
tmp = 0
for i in range(n):
  t += A[i]  
  if i%2 == 1:
    if t >= 0:
      tmp += abs(-1-t)
      t = -1      
  else:
    if t <= 0:
      tmp += abs(1-t)
      t = 1      
  
ans = tmp

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

Submission status: Accepted

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

def main():
    n = int(input())
    a = list(map(int, input().split()))
    a = list(accumulate(a))

    ans = 10**18

    for j in range(2):# 偶数行が正か奇数行が正
        ans2 = 0
        diff = 0
        for i in range(n):
            p = a[i] + diff
            # print(a[i],diff)
            if (i+j) % 2 == 0 and p <= 0:# 正になる
                ans2 += abs(p)+1
                diff += abs(p)+1
            elif (i+j) % 2 == 1 and p >= 0:# 負になる
                ans2 += abs(p)+1
                diff -= abs(p)+1

        ans = min(ans, ans2)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

def solver(_sign):
    s = A[0]
    count = 0

    if _sign:
        if s <= 0: # head is positive
            count += abs(s) + 1
            s = 1
    else:
        if s >= 0: # head is negative
            count += abs(s) + 1
            s = -1

    for a in A[1:]:
        prev = s
        sign = prev > 0
        s += a
        if s == 0:
            count += 1
            if sign: # previous is positive
                s = -1
            else: # prev is negative
                s = 1
        elif sign == (s > 0): # previous and current have the same sign
            count += abs(s)+1
            if s > 0:
                s = -1
            else:
                s = 1
        else:
            pass
    return count

print(min(solver(True), solver(False)))

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
ans=999999999999999
temp=True
for i in range(2):
  count=0
  temp=0
  if i==0:
    t=True
  else:
    t=False
  for j in a:
    temp=temp+j
    if t==True and temp<1:
      count=count+1-temp
      temp=1
    elif t==False and temp>-1:
      count=count+1+temp
      temp=-1
    if t==True:
      t=False
    else:
      t=True
  ans=min(ans,count)
print(ans)