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:
N = int(input())
A = [int(x) for x in input().split()]
ans_plusstart = 0
sum_plusstart = 0
ans_minusstart = 0
sum_minusstart = 0
if A[0] < 0:
    ans_plusstart += 1 - A[0]
    sum_minusstart = A[0]
    sum_plusstart = 1
else:
    ans_minusstart += 1 + A[0]
    sum_minusstart = -1
    sum_plusstart = max(1, A[0])
    if A[0] == 0:
        ans_plusstart = 1
for i in range(1, N):
    #print(sum_plusstart, ans_plusstart, sum_minusstart, ans_minusstart)
    if i % 2 == 0:  # スタートと同じ記号にしたい
        if A[i] + sum_plusstart > 0:
            sum_plusstart = A[i] + sum_plusstart
        if A[i] + sum_plusstart <= 0:
            ans_plusstart += 1-(A[i] + sum_plusstart)
            sum_plusstart = 1

        if A[i] + sum_minusstart < 0:
            sum_minusstart = A[i] + sum_minusstart
        if A[i] + sum_minusstart >= 0:
            ans_minusstart += 1 + A[i] + sum_minusstart
            sum_minusstart = -1

    else:  # スタートと違う記号にしたい
        if A[i] + sum_plusstart < 0:
            sum_plusstart = A[i] + sum_plusstart
        if A[i] + sum_plusstart >= 0:
            ans_plusstart += 1+A[i] + sum_plusstart
            sum_plusstart = -1

        if A[i] + sum_minusstart > 0:
            sum_minusstart = A[i] + sum_minusstart
        if A[i] + sum_minusstart <= 0:
            ans_minusstart += 1 - (A[i] + sum_minusstart)
            sum_minusstart = 1
print(min(ans_minusstart, ans_plusstart))

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int, input().split()))
c1, c2 = 0, 0
s = 0
for i in range(len(a)):
    S = s+a[i]
    if i%2 == 0:
        if S > 0:
            s = S
        else:
            c1 += abs(S)+1
            s = 1
    else:
        if S < 0:
            s = S
        else:
            c1 += abs(S)+1
            s = -1
s=0
for i in range(len(a)):
    S = s+a[i]
    if i%2 != 0:
        if S > 0:
            s = S
        else:
            c2 += abs(S)+1
            s = 1
    else:
        if S < 0:
            s = S
        else:
            c2 += abs(S)+1
            s = -1
print(min(c1, c2))

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
def ma():
  fg=[1,-1]
  ret = [0]*2
  tot = [0]*2
  il = range(n)
  jl = range(2)
  for i in il:
    for j in jl:
      tot[j]+=a[i]
      if tot[j]*fg[j]<=0:
        ret[j] += abs(fg[j] - tot[j])
        tot[j] += fg[j] - tot[j]
      fg[j]*=-1
  return min(ret)
print(ma())

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
fg=[1,-1]
ret = [0]*2
tot = [0]*2
il = range(n)
jl = range(2)
for i in il:
  for j in jl:
    tot[j]+=a[i]
    if tot[j]*fg[j]<=0:
      ret[j] += abs(fg[j] - tot[j])
      tot[j] += fg[j] - tot[j]
    fg[j]*=-1
print(min(ret))

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
fg=[1,-1]
ret = [0]*2
tot = [0]*2
for i in range(n):
  for j in range(2):
    tot[j]+=a[i]
    if tot[j]*fg[j]<=0:
      ret[j] += abs(fg[j] - tot[j])
      tot[j] += fg[j] - tot[j]
    fg[j]*=-1
print(min(ret))

Submission status: Accepted

Solution code:
import copy
n=int(input())
A=list(map(int,input().split()))
def solve(a,f):
  # print(f,a)
  ans=0
  for i in range(n):
    if i!=0: a[i]+=a[i-1]
    if not f:
      if a[i]>=0:
        ans+=a[i]+1
        a[i]=-1
    else:
      if a[i]<=0:
        ans+=a[i]*-1+1
        a[i]=1
    # print(a,ans,f)
    f^=True
  return ans
x=A.copy()
print(min(solve(A,True),solve(x,False)))

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

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

n = I()
a = LI()

def calc(flag):
    ans = 0
    now = 0
    for i in range(n):
        now += a[i]
        if flag == '+':
            if now <= 0:
                ans += 1-now
                now = 1
            flag = '-'
        else:
            if now >= 0:
                ans += now+1
                now = -1
            flag = '+'
    return ans

print(min(calc('+'),calc('-')))

Submission status: Accepted

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

#値を修正する場合、1か−1にすればよい
##そのためには、値の絶対値に1を足した数を加えればよい

#正、負のパターンと負、正のパターンの両方について算出し、小さい方を出力する
##没解だと、所与のA[0]の符号を基準としたまま、答えを提出していたが、
##当然、それが最適値であるとは限らない！！！

total = 0
ans = 0
total2 = 0
ans2 = 0

for i in range(N):
    total += A[i]
    #奇数番目を正にする
    if i % 2 == 0:
        #1より小さい == 0以下
        if total < 1:
            ans += 1 - total
            total = 1
    else:
        #0以上
        if total > -1:
            ans += (1 + total)
            total = -1

for i in range(N):
    total2 += A[i]
    #偶数番目を正にする
    if i % 2 == 1:
        if total2 < 1:
            ans2 += 1 - total2
            total2 = 1
    else:
        if total2 > -1:
            ans2 += 1 + total2
            total2 = -1

print(min(ans,ans2))

Submission status: Accepted

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
n=int(input())
a=list(map(int,input().split()))
s=0
A=0
for i in range(n):
    s+=a[i]
    if i%2==0:
        if s<=0:
            A+=1-s
            s=1
    else:
        if s>=0:
            A+=s+1
            s=-1
B=0
s=0
for i in range(n):
    s+=a[i]
    if i%2==1:
        if s<=0:
            B+=1-s
            s=1
    else:
        if s>=0:
            B+=s+1
            s=-1
print(A if A<B else B)

Submission status: Accepted

Solution code:
N = int(input())
a_lst = [int(x) for x in input().split()]
b_lst = []
for i in a_lst:
    b_lst.append(i)

def my_sign(num):
    return (num > 0) - (num < 0)

cnt_p = 0
cnt_n = 0
sum_lst = []
sum2_lst = []

for i in range(N): #偶数でマイナス、奇数でプラスの和
    sum_lst.append(a_lst[i]) if i == 0 else sum_lst.append(a_lst[i] + sum_lst[i - 1])
    if i%2 == 0 and sum_lst[i] >= 0:
        cnt_p += 1 + sum_lst[i]
        a_lst[i] -= 1 + sum_lst[i]
        sum_lst[i] = -1
    elif i%2 == 1 and sum_lst[i] <= 0:
        cnt_p += 1 + abs(sum_lst[i])
        a_lst[i] += 1 + abs(sum_lst[i])
        sum_lst[i] = 1
for i in range(N): #偶数でプラス、奇数でマイナスの和
    sum2_lst.append(b_lst[i]) if i == 0 else sum2_lst.append(b_lst[i] + sum2_lst[i - 1])
    if i%2 == 0 and sum2_lst[i] <= 0:
        cnt_n += 1 + abs(sum2_lst[i])
        b_lst[i] += 1 + abs(sum2_lst[i])
        sum2_lst[i] = 1
    elif i%2 == 1 and sum2_lst[i] >= 0:
        cnt_n += 1 + sum2_lst[i]
        b_lst[i] -= 1 + sum2_lst[i]
        sum2_lst[i] = -1
print(min(cnt_p, cnt_n))

Submission status: Accepted

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

# 1番目の値を正とする場合
ans1 = 0
sum = 0
flg = 1
for i in range(n):
    sum += a[i]
    if flg == 1:
        if sum < 0:
            flg = -1
        else:
            ans1 += sum + 1
            sum = -1
            flg = -1
    else:
        if sum > 0:
            flg = 1
        else:
            ans1 += (-sum) + 1
            sum = 1
            flg = 1

# 1番目の値を負とする場合
ans2 = 0
sum = 0
flg = -1
for i in range(n):
    sum += a[i]
    if flg == 1:
        if sum < 0:
            flg = -1
        else:
            ans2 += sum + 1
            sum = -1
            flg = -1
    else:
        if sum > 0:
            flg = 1
        else:
            ans2 += (-sum) + 1
            sum = 1
            flg = 1

print(min(ans1, ans2))

Submission status: Accepted

Solution code:
from sys import stdout
printn = lambda x: stdout.write(str(x))
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 999999999999999
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

n = inn()
a = inl()
ne = sum(a[::2])
no = sum(a[1::2])
p0 = (ne>no)
mn = BIG
for p0 in [True,False]:
 cnt = 0
 acc = 0
 #ddprint("ne {} no {} p0 {} a {}".format(ne,no,p0,a))
 for i in range(n):
    if (p0 if i%2==0 else not p0):
        x = max(0, 1-a[i]-acc)
        cnt += x
        acc += a[i]+x
    else:
        x = max(0, a[i]+acc+1)
        cnt += x
        acc += a[i]-x
    #ddprint("cnt {} acc {}".format(cnt,acc))
 mn = min(mn,cnt)
print(mn)

Submission status: Accepted

Solution code:
def countave(n , a):
    ans = 100000000000000

    for i in range(2 , 4):
        kei = 0
        forans = 0
        #偶数+
        if i % 2 == 0:
            fast = 1
        else:
            fast = -1
        for w in range(n):
            if fast < 0 and kei + int(a[w]) >= 0:
                forans += abs(kei + int(a[w])) + 1
                kei = -1
                fast = 1
            elif fast > 0 and kei + int(a[w]) <= 0:
                forans += abs(kei + int(a[w])) + 1
                kei = 1
                fast = -1
            else:
                kei += int(a[w])
                fast *= -1
        ans = min(ans , forans)

    return ans

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def countave(n , a):
    ans = 100000000000000

    for i in range(2):
        kei = 0
        forans = 0
        for w in range(n):
            if (w + i) % 2:
                if kei + int(a[w]) > -1:
                    forans += abs(kei + int(a[w])) + 1
                    kei = -1
                else:
                    kei += int(a[w])
            else:
                if kei + int(a[w]) < 1:
                    forans += abs(kei + int(a[w])) + 1
                    kei = 1
                else:
                    kei += int(a[w])

        ans = min(ans , forans)

    return ans

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
N=int(input())

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

wa=0
ans=0
for i in range(N):
    wa+=A[i]
    if i%2:
        if wa<1:
            ans+=1-wa
            wa=1
    else:
        if wa>-1:
            ans+=(1+wa)
            wa=-1
wa=0
ans2=0
for i in range(N):
    wa+=A[i]
    if (i+1)%2:
        if wa<1:
            ans2+=1-wa
            wa=1
    else:
        if wa>-1:
            ans2+=1+wa
            wa=-1

print(min(ans,ans2))

Submission status: Accepted

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

s_pos = 0
s_neg = 0

# start neg val
cum = 0
for i in range(n):
    cum += a[i]
    if i % 2 == 0 and cum >= 0:
        s_neg += abs(cum) + 1
        cum = -1
    if i % 2 != 0 and cum <= 0:
        s_neg += abs(cum) + 1
        cum = 1

# start pos val
cum = 0
for i in range(n):
    cum += a[i]
    if i % 2 == 0 and cum <= 0:
        s_pos += abs(cum) + 1
        cum = 1
    if i % 2 != 0 and cum >= 0:
        s_pos += abs(cum) + 1
        cum = -1

ans = min(s_pos, s_neg)
print(ans)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect
from heapq import heappush, heappop

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

n = INT()
A = LIST()

def solve(lis):
	lis = lis.copy()
	tmp_sum = lis[0]
	lis = lis[1:]
	cnt = 0
	for x in lis:
		if (tmp_sum + x) * tmp_sum < 0:  # 異符号
			tmp_sum += x
		else:
			cnt += abs((-1)**(tmp_sum>0)*(abs(tmp_sum)+1)-x)
			tmp_sum = (-1)**(tmp_sum>0)
	return cnt

if A[0] > 0:
	ans = solve(A)
	B = A.copy()
	B[0] = -1
	ans = min(ans, solve(B)+abs(A[0]+1))
elif A[0] < 0:
	ans = solve(A)
	B = A.copy()
	B[0] = 1
	ans = min(ans, solve(B)+abs(A[0]-1))
else:
	A[0] = 1
	ans = solve(A)+1
	A[0] = -1
	ans = min(ans, solve(A)+1)
print(ans)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect
from heapq import heappush, heappop

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

n = INT()
A = LIST()

def solve(lis):
	lis = lis.copy()
	tmp_sum = lis[0]
	lis = lis[1:]
	cnt = 0
	for x in lis:
		if (tmp_sum + x) * tmp_sum < 0:  # 異符号
			tmp_sum += x
		else:
			 if tmp_sum > 0:
			 	cnt += abs(-tmp_sum-1-x)
			 	tmp_sum = -1
			 else:
			 	cnt += abs(-tmp_sum+1-x)
			 	tmp_sum = 1
	return cnt

if A[0] > 0:
	ans = solve(A)
	B = A.copy()
	B[0] = -1
	ans = min(ans, solve(B)+abs(A[0]+1))
elif A[0] < 0:
	ans = solve(A)
	B = A.copy()
	B[0] = 1
	ans = min(ans, solve(B)+abs(A[0]-1))
else:
	A[0] = 1
	ans = solve(A)+1
	A[0] = -1
	ans = min(ans, solve(A)+1)
print(ans)

Submission status: Accepted

Solution code:
import  copy
n = int(input())
a = list(map(int, input().split()))
check = copy.deepcopy(a)
#####segfunc######
def segfunc(x,y):
    return x+y

def init(init_val):
    #set_val
    for i in range(len(init_val)):
        seg[i+num-1]=init_val[i]   
    #built
    for i in range(num-2,-1,-1) :
        seg[i]=segfunc(seg[2*i+1],seg[2*i+2]) 
    
def update(k,x):
    k += num-1
    seg[k] = x
    while k:
        k = (k-1)//2
        seg[k] = segfunc(seg[k*2+1],seg[k*2+2])
    
def query(p,q):
    if q<=p:
        return ide_ele
    p += num-1
    q += num-2
    res=ide_ele
    while q-p>1:
        if p&1 == 0:
            res = segfunc(res,seg[p])
        if q&1 == 1:
            res = segfunc(res,seg[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = segfunc(res,seg[p])
    else:
        res = segfunc(segfunc(res,seg[p]),seg[q])
    return res

#####単位元######
ide_ele = 0
num =2**(n-1).bit_length()
seg=[ide_ele]*(2*num - 1)
init(a)
ans_1 = 0
pre_sum = (-1) * a[0]
for i in range(n):
    q_sum = query(0,i+1)
    if q_sum * pre_sum >= 0:
        if pre_sum < 0:
            update(i, abs(pre_sum) + 1)
        else:
            update(i, (-1) * (pre_sum+1))
    pre_sum = query(0,i+1)
for i in range(n):
    ans_1 += abs(check[i] - seg[i + num - 1])
if a[0] == 0:
    a[0] = 1
else:
    if a[0] < 0:
        a[0] = 1
    else:
        a[0] = -1
ans_2 = 0
pre_sum = (-1) * a[0]
init(a)
for i in range(n):
    q_sum = query(0,i+1)
    if q_sum * pre_sum >= 0:
        if pre_sum < 0:
            update(i, abs(pre_sum) + 1)
        else:
            update(i, (-1) * (pre_sum+1))
    pre_sum = query(0,i+1)
for i in range(n):
    ans_2 += abs(check[i] - seg[i + num - 1])
print(min(ans_1,ans_2))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
n = int(input())
a = list(map(int,input().split()))
def solve(cnt,current_sum):
    for i in range(n-1):
        if current_sum * (current_sum + a[i+1]) < 0:#符号が違う
            current_sum += a[i+1]
            cnt += 0#そのまま
        elif current_sum < 0:
            cnt += 1 - (current_sum + a[i+1])
            current_sum = 1 
        else:
            cnt += (current_sum + a[i+1]) +1 
            current_sum = -1
    return cnt
if a[0] > 0:
    print(min(solve(0,a[0]),solve(1+abs(a[0]),-1)))
elif a[0] < 0:
    print(min(solve(0,a[0]),solve(1+abs(a[0]),1)))
else:
    print(min(solve(1,1),solve(1,-1)))

Submission status: Accepted

Solution code:
import sys
import itertools

input = sys.stdin.readline


def main():
    N = int(input())
    A = [int(x) for x in input().split()]


    accu = list(itertools.accumulate(A))

    ans1 = 0
    ruiseki = 0
    for i, x in enumerate(accu):
        if i % 2 == 0:
            if ruiseki + x <= 0:
                ans1 += 1 + abs(ruiseki + x)
                ruiseki += 1 + abs(ruiseki + x)
        else:
            if ruiseki + x >= 0:
                ans1 += 1 + abs(ruiseki + x)
                ruiseki += -1 - abs(ruiseki + x)

    ans2 = 0
    ruiseki = 0
    for i, x in enumerate(accu):
        if i % 2 != 0:
            if ruiseki + x <= 0:
                ans2 += 1 + abs(ruiseki + x)
                ruiseki += 1 + abs(ruiseki + x)
        else:
            if ruiseki + x >= 0:
                ans2 += 1 + abs(ruiseki + x)
                ruiseki += -1 - abs(ruiseki + x)

    print(min(ans1, ans2))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
A = list(map(int,input().split()))
s = max(A[0],1)
cnt1 = abs(A[0]-s) #sを正にするまで
for a in A[1:]:
    if s>0:
        b=min(a, -s-1) #aを何の値にするかがb
    if s<0:
        b=max(a,-s+1)
    s += b #bを足してs更新
    cnt1 += abs(a-b)

s = min(A[0],-1)
cnt2 = abs(A[0]-s)
for a in A[1:]:
    if s>0:
         b=min(a, -s-1) #aを何の値にするかがb
    if s<0:
        b=max(a,-s+1)
    s += b #bを足してs更新
    cnt2 += abs(a-b)
print(min(cnt1,cnt2))

Submission status: Accepted

Solution code:
n = int(input())
A = list(map(int, input().split()))
ans1 = 0
acc = 0
d = 1
for a in A:
    if (acc + a) * d > 0:
        acc += a
    else:
        ans1 += abs(1 - (acc + a) * d)
        acc = d
    d *= -1
ans2 = 0
acc = 0
d = -1
for a in A:
    if (acc + a) * d > 0:
        acc += a
    else:
        ans2 += abs(1 - (acc + a) * d)
        acc = d
    d *= -1
print(min(ans1, ans2))

Submission status: Accepted

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

#前から貪欲でよいか
#a[0]を正か負に定めて貪欲

#a[0]が正と仮定してよい
if a[0]<0:
    for i in range(n):
        a[i]*=-1

#場合分け用
a2 = [a[i] for i in range(n)]


ans1 = 0
if not a[0]:
    ans1 += 1
    a[0] = 1
sm = a[0]

for i in range(1,n):
    sm2 = sm + a[i]
    #print(sm,sm2)
    if sm2*sm>=0:
        if sm<0:#sm+a[i]=1
            ans1 += abs((1-sm)-a[i])
            a[i]=1-sm
            sm = 1
            
        else:#sm+a[i] = -1
            ans1 += abs(-1-sm-a[i])
            a[i]=-1-sm
            sm = -1
    else:
        sm=sm2

ans2 = abs(-1-a2[0])
a2[0]=-1
sm = -1

for i in range(1,n):
    sm2 = sm + a2[i]
    if sm2*sm>=0:
        if sm<0:#sm+a[i]=1
            ans2 += abs((1-sm)-a2[i])###a[i]と間違えるから関数として定義してa1,a2投げる
            a2[i] = 1-sm
            sm = 1
        else:#sm+a[i] = -1
            ans2 += abs(-1-sm-a2[i])###
            a2[i]=-1-sm
            sm = -1
    else:
        sm =sm2
   

print(min(ans1,ans2))

Submission status: Accepted

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

s = max(A[0], +1)
ans_p = abs(A[0]-s)
for a in A[1:]:
    if s>0: b=min(a, -s-1)
    if s<0: b=max(a, -s+1)
    s += b
    ans_p += abs(a-b)

s = min(A[0], -1)
ans_n = abs(A[0]-s)
for a in A[1:]:
    if s>0: b=min(a, -s-1)
    if s<0: b=max(a, -s+1)
    s += b
    ans_n += abs(a-b)

print(min(ans_p, ans_n))

Submission status: Accepted

Solution code:
# input = sys.stdin.readline
from bisect import *
from collections import *
from heapq import *
# import functools
# import itertools
# import math

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

def main(c,temp):

    if temp>0:
        flag=1
    elif temp<0:
        flag=0
    for i in range(1,n):
        temp+=A[i]
        if flag:
            if temp>=0:
                c+=temp-(-1)
                temp=-1
            flag=0
        else:
            if temp<=0:
                c+=1-temp
                temp=1
            flag=1
    return(c)

temp=A[0]
if temp:
    a=main(0,temp)
    if temp>0:
        b=main(temp - (-1),-1)
    else:
        b=main(1-temp,1)
    print(min(a,b))
else:
    temp=1
    a=main(1,temp)
    temp=-1
    b=main(1,temp)
    print(min(a,b))

Submission status: Accepted

Solution code:
import copy
n = int(input())

numbers = list(map(int, input().split()))
numbers1 = copy.copy(numbers)
counter = 0
counter2 = 0
sum_in = 0
sum_in1 = 0

for i in range(len(numbers)):
    sum_in += numbers[i]
    if i % 2 == 0:
        if sum_in <= 0:
            sub = abs(sum_in) + 1
            sum_in += sub
            numbers[i] += sub
            counter += sub
    else:
        if sum_in >= 0:
            sub = abs(sum_in) + 1
            sum_in -= sub
            numbers[i] -= sub
            counter += sub

for i in range(len(numbers1)):
    sum_in1 += numbers1[i]

    if i % 2 != 0:
        if sum_in1 <= 0:
            sub = abs(sum_in1) + 1
            sum_in1 += sub
            numbers1[i] += sub
            counter2 += sub
    else:
        if sum_in1 >= 0:
            sub = abs(sum_in1) + 1
            sum_in1 -= sub
            numbers1[i] -= sub
            counter2 += sub

print(min([counter2, counter]))

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,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:
n = list(input().split())

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

# flg:True プラスの想定
def chk(A, flg):
    #print("-------")
    # 初期値
    x=0
    ans =0
    for a in A:
        # 今までの合計
        x += a
        
        # 想定と違ったら、1との差分を増減する
        if flg==True and x < 1:
            ans +=1-x
            # xは1に変える
            x=1
        elif flg == False and x> -1:
            ans += x+1
            x=-1
        #print(x)
        flg = not flg

    return(ans)
print(min(chk(A, True),chk(A, False)))

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def main():
    n = II()
    aa = LI()
    # +から始めるパターン
    cs = 0
    ans1 = 0
    for i, a in enumerate(aa):
        cs += a
        if i % 2:
            if cs >= 0:
                ans1 += abs(-1 - cs)
                cs = -1
        else:
            if cs <= 0:
                ans1 += abs(1 - cs)
                cs = 1
    # -から始めるパターン
    cs = 0
    ans2 = 0
    for i, a in enumerate(aa):
        cs += a
        if i % 2:
            if cs <= 0:
                ans2 += abs(1 - cs)
                cs = 1
        else:
            if cs >= 0:
                ans2 += abs(-1 - cs)
                cs = -1
    print(min(ans1,ans2))

main()

Submission status: Accepted

Solution code:
import numpy as np
N = int(input())
A = list(map(int, input().split()))

res_plus = np.cumsum(A)
res_minus = np.cumsum(A)
ans_plus = 0
ans_minus = 0

tmp_tmp = 0
# 奇数項を正とする
for i in range(N):
    res_plus[i] += tmp_tmp
    if i % 2 == 0:         # 奇数項   
        if res_plus[i] > 0:
            pass
        else:
            tmp = 1 - res_plus[i]
            ans_plus += tmp
            tmp_tmp += tmp
    else:                  # 偶数項
        if res_plus[i] < 0:
            pass
        else:
            tmp = res_plus[i] + 1
            ans_plus += tmp
            tmp_tmp -= tmp


tmp_tmp = 0
# 奇数項を負とする
for i in range(N):
    res_minus[i] += tmp_tmp
    if i % 2 == 0:      # 奇数項
        if res_minus[i] < 0:
            pass
        else:
            tmp = res_minus[i] + 1
            ans_minus += tmp
            tmp_tmp -= tmp
    else:               # 偶数項
        if res_minus[i] > 0:
            pass
        else:
            tmp = 1 - res_minus[i]
            ans_minus += tmp
            tmp_tmp += tmp

##print(ans_minus, ans_plus)
print(min(ans_plus, ans_minus))

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
m1 = 0
cnt1 = 0
f = 1
for i in range(n):
    f *= -1
    m1 += a[i]
    if f == 1:
        if m1 <= 0:
            cnt1 += f-m1
            m1 += f-m1
    else:
        if m1 >= 0:
            cnt1 += m1-f
            m1 -= m1-f
m2 = 0
cnt2 = 0
f = -1
for i in range(n):
    f *= -1
    m2 += a[i]
    if f == 1:
        if m2 <= 0:
            cnt2 += f-m2
            m2 += f-m2
    else:
        if m2 >= 0:
            cnt2 += m2-f
            m2 -= m2-f

print(min(cnt1, cnt2))

Submission status: Accepted

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

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

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

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 solve(cumsum, prev_plus):
    cnt = 0
    total_sum = 0
    for i, c in enumerate(cumsum):
        c = c + total_sum
        if prev_plus:
            # if minus, ignore
            if c < 0:
                pass
            else:
                cnt += (c - (-1))
                total_sum -= (c - (-1))
        else:
            if c > 0:
                pass
            else:
                cnt += (1 - c)
                total_sum += (1 - c)
        prev_plus = not prev_plus
    return cnt


def main():
    N = I()
    A = LI()
    cumsum = [0]
    for i in range(N):
        cumsum.append(A[i] + cumsum[i])
    cumsum = cumsum[1:]
    prev_plus = cumsum[0] > 0
    a1 = solve(cumsum, True)
    a2 = solve(cumsum, False)
    print(min(a1, a2))

main()

Submission status: Accepted

Solution code:
def k(n, a, p):
    x = 0
    c = 0
    for i in range(n):
        s = x + a[i]
        if p and s > 0 or not p and s < 0: x = s
        else:
            c += abs(s) + 1
            if p: x = 1
            else: x = -1
        p = not p
    return c

n = int(input())
a = [int(x) for x in input().split()]
print(min(k(n, a, True), k(n, a, False)))

Submission status: Accepted

Solution code:
n = int(input())

a = list(map(int,input().split()))
b = [i for i in a]


def solve(cnt,A,N):
    sumA=A[0]
    for i in range(1, N):
        if sumA>0:
            if sumA+A[i]>=0:
                r = A[i]
                A[i]=-sumA-1
                cnt+=abs(r-A[i])
        else:
            if sumA+A[i]<=0:
                r = A[i]
                A[i]=-sumA+1
                cnt+=abs(r-A[i])

        sumA+=A[i]
    return cnt

cnt1=0
if b[0]<=0:
    ini=b[0]
    b[0]=1
    cnt1=abs(1-ini)


ans1=solve(cnt1,b,n)
cnt2=0
if a[0]>=0:
    ini=a[0]
    a[0]=-1
    cnt2=abs(-1-ini)


ans2=solve(cnt2,a,n)

print(min(ans1,ans2))

Submission status: Accepted

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

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

b = a[:]
acc = 0

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

c = a[:]
acc = 0

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

ans = min(sum(abs(ai-bi) for ai, bi in zip(a, b)), sum(abs(ai-ci) for ai, ci in zip(a, c)))

print(ans)

Submission status: Accepted

Solution code:
#sequence
n=int(input())
lists=list(map(int,input().split()))
a=0
sum1=0
#奇数番目の項が-,偶数番目の項が＋の場合の最小値
for i in range(n):
    sum1+=lists[i]
    if i%2==0:
        if sum1>=0:
            a+=(sum1+1)
            sum1=-1
        elif sum1<0:
            pass
    elif  i%2!=0:
        if sum1<=0:
            a+=(1-sum1)
            sum1=1
        elif sum1>0:
            pass

b=0
#奇数番目の項が＋、偶数番目の項が−の場合の最小値
sum2=0
for i in range(n):
    sum2+=lists[i]
    if i%2!=0:
        if sum2>=0:
            b+=(sum2+1)
            sum2=-1
        elif sum2<0:
            pass
    elif  i%2==0:
        if sum2<=0:
            b+=(1-sum2)
            sum2=1
        elif sum2>0:
            pass
print(min(a,b))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n=int(input())
a=list(map(int,input().split()))

v=[]
for s in (1,-1):
    x=a[::]
    hugou=[s*(-1)**i for i in range(n)]
    total=0
    for i in range(n):
        if (total+x[i])*hugou[i]<=0:
            x[i]=hugou[i]-total
        total+=x[i]
    v.append(sum(abs(a[i]-x[i]) for i in range(n)))
print(min(v))

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,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:
n = int(input())
arr = [0] + list(map(int, input().split()))
cnt = 0
ans = float('inf')
for sign in [-1, 1]:
    res = 0
    partial_sum = 0
    A = [x for x in arr]
    for i in range(n):
        partial_sum += A[i]
        diff = sign - (partial_sum + A[i+1]                )
        if sign < 0:
            diff = min(diff, 0)
        else:
            diff = max(diff, 0)
        res += abs(diff)
        A[i+1] += diff
        sign *= -1
    ans = min(ans, res)
print(ans)

Submission status: Accepted

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

def exec(sign):
    a = [x for x in arr]
    res = 0

    x = 0
    for i in range(n):
        x += a[i]
        tmp = sign - (x + a[i+1])
        if sign < 0:
            tmp = min(tmp, 0)
        else:
            tmp = max(tmp, 0)
        res += abs(tmp)
        a[i+1] += tmp
        sign *= (-1)
    return res

print(min(exec(1), exec(-1)))