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())
l=list(map(int,input().split()))
s=[l[0]]
for i in range(1,n):
    s.append(s[i-1]+l[i])
x,y=0,0
for i in range(n):
    if s[i]*((-1)**i)<=0:
        x+=abs(s[i]-(-1)**i)
        s[i]=(-1)**i
    if i+1<=n-1:
        s[i+1]=s[i]+l[i+1]
s=[l[0]]
for i in range(1,n):
    s.append(s[i-1]+l[i])
for i in range(n):
    if s[i]*((-1)**(i+1))<=0:
        y+=abs(s[i]-(-1)**(i+1))
        s[i]=(-1)**(i+1)
    if i+1<=n-1:
        s[i+1]=s[i]+l[i+1]
print(min(x,y))

Submission status: Accepted

Solution code:
n = int(input())
num_list = list(map(int, input().split()))
count = 0
sum_ = num_list[0]
if sum_ > 0:
    for i in range(1, n):
        sum_ += num_list[i]
        if i%2 == 0:
            if sum_ <= 0:
                count += abs(sum_) + 1
                sum_ = 1
        else:
            if sum_ >= 0:
                count += abs(sum_) + 1
                sum_ = -1
    count1 = count
    
    count = 0
    sum_ = -1
    for i in range(1, n):
        sum_ += num_list[i]
        if i%2 == 1:
            if sum_ <= 0:
                count += abs(sum_) + 1
                sum_ = 1
        else:
            if sum_ >= 0:
                count += abs(sum_) + 1
                sum_ = -1
    count2 = count + num_list[0] + 1
    
    print(min(count1, count2))
elif sum_ < 0:
    for i in range(1, n):
        sum_ += num_list[i]
        if i%2 == 1:
            if sum_ <= 0:
                count += abs(sum_) + 1
                sum_ = 1
        else:
            if sum_ >= 0:
                count += abs(sum_) + 1
                sum_ = -1
    count1 = count
    
    count = 0
    sum_ = 1
    for i in range(1, n):
        sum_ += num_list[i]
        if i%2 == 0:
            if sum_ <= 0:
                count += abs(sum_) + 1
                sum_ = 1
        else:
            if sum_ >= 0:
                count += abs(sum_) + 1
                sum_ = -1
    count2 = count + abs(num_list[0]) + 1
    
    print(min(count1, count2))
    
else:
    sum_ = -1
    for i in range(1, n):
        sum_ += num_list[i]
        if i%2 == 1:
            if sum_ <= 0:
                count += abs(sum_) + 1
                sum_ = 1
        else:
            if sum_ >= 0:
                count += abs(sum_) + 1
                sum_ = -1
    count1 = count + 1
    
    count = 0
    sum_ = 1
    for i in range(1, n):
        sum_ += num_list[i]
        if i%2 == 0:
            if sum_ <= 0:
                count += abs(sum_) + 1
                sum_ = 1
        else:
            if sum_ >= 0:
                count += abs(sum_) + 1
                sum_ = -1
    count2 = count + 1    

    print(min(count1, count2))

Submission status: Accepted

Solution code:

def get_ans(ans_init, sum_init, A):
    ans = ans_init
    sum = sum_init
    for i in range(1, len(A)):
        a = A[i]
        prev_sum = sum
        sum += a
        if sum * prev_sum >= 0:
            ans += abs(prev_sum+a)+1
            if prev_sum > 0:
                sum = -1
            else:
                sum = 1
    return ans


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

ans_1 = 0
sum_1 = A[0]
if A[0] <= 0:
    ans_1 += abs(A[0])+1
    sum_1 = 1

ans_1 = get_ans(ans_1, sum_1, A)

ans_2 = 0
sum_2 = A[0]
if A[0] >= 0:
    ans_2 += abs(A[0])+1
    sum_2 = -1

ans_2 = get_ans(ans_2, sum_2, A)

print(min(ans_1, ans_2))

Submission status: Accepted

Solution code:
n = int(input())
a = [int(x) for x in input().split()]
ans = 2**60

if a[0] == 0:
  s = 1
  cnt = 1
  for i in range(1,n):
    ns = s + a[i]
    if s * ns < 0:
      s = ns
      continue
    else:
      cnt += abs(ns)+1
      s = -1 if ns > 0 else 1
  ans = min(ans, cnt)

  s = -1
  cnt = 1
  for i in range(1,n):
    ns = s + a[i]
    if s * ns < 0:
      s = ns
      continue
    else:
      cnt += abs(ns)+1
      s = -1 if ns > 0 else 1
  ans = min(ans, cnt)
  
else:
  s = a[0]
  cnt = 0
  for i in range(1,n):
    ns = s + a[i]
    if s * ns < 0:
      s = ns
      continue
    else:
      cnt += abs(ns)+1
      s = -1 if ns > 0 else 1
  ans = min(ans, cnt)
  
  s = -1 if a[0] > 0 else 1
  cnt = abs(a[0])+1
  for i in range(1,n):
    ns = s + a[i]
    if s * ns < 0:
      s = ns
      continue
    else:
      cnt += abs(ns)+1
      s = -1 if ns > 0 else 1
  ans = min(ans, cnt)

print(ans)

Submission status: Accepted

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

sums_1,sums_2 = 0,0
ans_1,ans_2 = 0,0

for i in range(len(aa)):
    tmp = sums_1 + aa[i]
    if (i % 2 == 0 and tmp <= 0) or (i % 2 == 1 and tmp >= 0):
        sums_1 = (-1)**(i % 2)
        ans_1 += abs(tmp)+1
    else:
        sums_1 = tmp

for i in range(len(aa)):
    tmp = sums_2 + aa[i]
    if (i % 2 == 0 and tmp >= 0) or (i % 2 == 1 and tmp <= 0):
        sums_2 = (-1)**(i % 2 + 1)
        ans_2 += abs(tmp)+1
    else:
        sums_2 = tmp

print(min(ans_1,ans_2))

Submission status: Accepted

Solution code:
n=int(input())
l=[int(i) for i in input().split()]
chk1=ans1=chk2=ans2=0

for a,i in enumerate(l):
    chk1+=i
    chk2+=i
    if a%2:
        if chk1<=0:
            ans1+=1-chk1
            chk1=1
        if chk2>=0:
            ans2+=chk2+1
            chk2=-1
    else:
        if chk1>=0:
            ans1+=1+chk1
            chk1=-1
        if chk2<=0:
            ans2+=1-chk2
            chk2=1
print(min(ans1,ans2))

Submission status: Accepted

Solution code:
n = int(input())
a_list = list(map(int,input().split()))
ans = float('inf')

for i in [1,-1]:
    ans_i = 0
    sums  = 0
    for a in a_list:
        sums += a
        if sums*i <= 0:
            ans_i += abs(sums-i)
            sums = i
        i *= -1
    ans = min(ans,ans_i)

print(ans)

Submission status: Accepted

Solution code:
def culc(a, plus):
    sum = 0
    ans = 0
    for i in range(len(a)):
        sum += a[i]
        if plus:
            if sum <= 0:
                ans += abs(sum) + 1
                sum = 1
        else:
            if sum >= 0:
                ans += abs(sum) + 1
                sum = -1
        plus = not(plus)
    return ans

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

ans1 = culc(a, True)
ans2 = culc(a, False)

print(min(ans1, ans2))

Submission status: Accepted

Solution code:

def culc(a, plus):
    sum = 0
    ans = 0
    for i in range(len(a)):
        sum += a[i]
        if plus:
            if sum <= 0:
                ans += abs(sum) + 1
                sum = 1
        else:
            if sum >= 0:
                ans += abs(sum) + 1
                sum = -1
        plus = not(plus)
    return ans

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

plus = None
if a[0] >= 0:
    plus = True
else:
    plus = False

ans1 = culc(a, plus)
ans2 = culc(a, not(plus))

print(min(ans1, ans2))

Submission status: Accepted

Solution code:
#059-C
import copy
n=int(input())
a=list(map(int,input().split()))
a1=copy.deepcopy(a)
a2=copy.deepcopy(a)
def pl(n):
    if n>0:
        return 1
    elif n==0:
        return 0
    else:
        return -1
s1=0
s2=0
c1=0
c2=0
b=1
for i in range(n):
    if b==-1:
        if pl(s1+a1[i])!=-1:
            t=s1+a1[i]+1
            a1[i]-=t
            c1+=t
        s1+=a1[i]
        b=1
    else:
        if pl(s1+a1[i])!=1:
            t=-s1-a1[i]+1
            a1[i]+=t
            c1+=t
        s1+=a1[i]
        b=-1

b=-1
for i in range(n):
    if b==-1:
        if pl(s2+a2[i])!=-1:
            t=s2+a2[i]+1
            a2[i]-=t
            c2+=t
        s2+=a2[i]
        b=1
    else:
        if pl(s2+a2[i])!=1:
            t=-s2-a2[i]+1
            a2[i]+=t
            c2+=t
        s2+=a2[i]
        b=-1
print(min(c1,c2))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
n = int(input())
an = list(map(int, input().split()))

#プラス始まり
if an[0] > 0:
    sum = an[0]
    ans = 0
else:
    sum = 1
    ans = abs(an[0])+1

for i in range(1,n):
    if sum * (sum + an[i]) < 0:
        sum += an[i]
    else:
        if sum > 0:
            ans += abs(sum + an[i] + 1)
            sum = -1
        else:
            ans += abs(sum + an[i] - 1)
            sum = 1
ans1 = ans

#-始まり
if an[0] < 0:
    sum = an[0]
    ans = 0
else:
    sum = -1
    ans = abs(an[0])+1

for i in range(1, n):
    if sum * (sum + an[i]) < 0:
        sum += an[i]
    else:
        if sum > 0:
            ans += abs(sum + an[i] + 1)
            sum = -1
        else:
            ans += abs(sum + an[i] - 1)
            sum = 1

# print(ans1, ans)
print(min([ans1, ans]))

Submission status: Accepted

Solution code:
#結局これもパターン全列挙(2パターン)か。
#判別しようと無駄な努力をしてしまった。
def 解():
    iN = int(input())
    aA = [int(_) for _ in input().split()]
    def buildDiff(bF):
        iC = 0
        iS = 0
        for a in aA:
            iS += a
            if bF:
                if iS >= 0:
                    iC += iS + 1
                    iS = -1
                bF = 0
            else:
                if iS <= 0:
                    iC += -1 * iS + 1
                    iS = 1
                bF = 1
        return iC
    print(min(buildDiff(1),buildDiff(0)))
解()

Submission status: Accepted

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

a_orig = a[:]

ans1 = 0
ans2 = 0
tot = [0 for i in range(n)]
tot[0] = a[0]

if a[0] <= 0:
    a[0] = 1
    tot[0] = 1


for i in range(1, n):
    tot[i] = tot[i-1] + a[i]
    if i % 2 == 0:
        if tot[i] <= 0:
            tot[i] = 1
            a[i] = tot[i] - tot[i-1]

    else:
        if tot[i] >= 0:
            tot[i] = -1
            a[i] = tot[i] - tot[i-1]

for i in range(n):
    ans1 += abs(a[i]-a_orig[i])



a = a_orig[:]
tot = [0 for i in range(n)]
tot[0] = a[0]

if a[0] >= 0:
    a[0] = -1
    tot[0] = -1

for i in range(1, n):
    tot[i] = tot[i-1] + a[i]
    if i % 2 == 1:
        if tot[i] <= 0:
            tot[i] = 1
            a[i] = tot[i] - tot[i-1]

    else:
        if tot[i] >= 0:
            tot[i] = -1
            a[i] = tot[i] - tot[i-1]

for i in range(n):
    ans2 += abs(a[i]-a_orig[i])
print(min(ans1, ans2))

Submission status: Accepted

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

#奇数項を正にする
oddS = (A[0] if A[0] > 0 else 1)
oddtotal = (0 if A[0] > 0 else 1 - A[0])
for i in range(1, N):
    if oddS > 0:
        if oddS + A[i] < 0: oddS += A[i]
        else:
            oddtotal += abs(-1 - (oddS + A[i]))
            oddS = -1
    elif oddS < 0:
        if oddS + A[i] > 0: oddS += A[i]
        else: 
            oddtotal += 1 - (oddS + A[i])
            oddS = 1

#偶数項を正にする
eS = (A[0] if A[0] < 0 else -1)
etotal = (0 if A[0] < 0 else A[0] + 1)
for i in range(1, N):
    if eS > 0:
        if eS + A[i] < 0: eS += A[i]
        else:
            etotal += abs(-1 - (eS + A[i]))
            eS = -1
    elif eS < 0:
        if eS + A[i] > 0: eS += A[i]
        else: 
            etotal += 1 - (eS + A[i])
            eS = 1

print(min(oddtotal, etotal))

Submission status: Accepted

Solution code:
n = int(input())
a = tuple(list(map(int, input().split())))
#aをtupleにしておかないとb = aとしたときにb変更するとa変更されてしまう リストーのコピー
def puramai(a):
    b = list(a)
    hikaku = 0
    ans = 0
    for i in range(n):
        if i % 2 == 0 and hikaku + b[i] <= 0:
            b[i] = -hikaku+1
            ans += abs(b[i]-a[i])
        
        elif i % 2 != 0 and hikaku + b[i] >= 0:
            b[i] = -hikaku-1
            ans += abs(b[i]-a[i])
        
        hikaku += b[i]
    return ans

def maipura(a):
    b = list(a)
    hikaku = 0
    ans = 0
    for i in range(n):
        if i % 2 == 0 and hikaku + b[i] >= 0:
            b[i] = -hikaku-1
            ans += abs(b[i]-a[i])
        
        elif i % 2 != 0 and hikaku + b[i] <= 0:
            b[i] = -hikaku+1
            ans += abs(b[i]-a[i])
        
        hikaku += b[i]
    return ans
print(min(maipura(a), puramai(a)))

Submission status: Accepted

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

def puramai(a):
    b = list(a)
    hikaku = 0
    ans = 0
    for i in range(n):
        if i % 2 == 0 and hikaku + b[i] <= 0:
            b[i] = -hikaku+1
            ans += abs(b[i]-a[i])
        
        elif i % 2 != 0 and hikaku + b[i] >= 0:
            b[i] = -hikaku-1
            ans += abs(b[i]-a[i])
        
        hikaku += b[i]
    return ans

def maipura(a):
    b = list(a)
    hikaku = 0
    ans = 0
    for i in range(n):
        if i % 2 == 0 and hikaku + b[i] >= 0:
            b[i] = -hikaku-1
            ans += abs(b[i]-a[i])
        
        elif i % 2 != 0 and hikaku + b[i] <= 0:
            b[i] = -hikaku+1
            ans += abs(b[i]-a[i])
        
        hikaku += b[i]
    return ans
print(min(maipura(a), puramai(a)))

Submission status: Accepted

Solution code:
N = int( input())
A = list( map( int, input().split()))
ans = 10**15
for i in [1, -1]:
    ansi, sums = 0, 0
    for a in A:
        sums += a
        if sums*i <= 0:
            ansi += abs(sums-i)
            sums = i
        i *= -1
    ans = min( ans, ansi)
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
INF = float("inf")
YES, Yes, yes, NO, No, no = "YES", "Yes", "yes", "NO", "No", "no"
dy4, dx4 = [0, 1, 0, -1], [1, 0, -1, 0]
dy8, dx8 = [0, -1, 0, 1, 1, -1, -1, 1], [1, 0, -1, 0, 1, 1, -1, -1]


def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W


def ceil(a, b):
    return (a + b - 1) // b


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

    ans = INF

    cost = 0
    total = 0
    for i, a in enumerate(A):
        total += a
        if i % 2 == 0 and total <= 0:
            cost += abs(total) + 1
            total = 1
        elif i % 2 == 1 and total >= 0:
            cost += abs(total) + 1
            total = -1
    ans = min(ans, cost)

    cost = 0
    total = 0
    for i, a in enumerate(A):
        total += a
        if i % 2 == 1 and total <= 0:
            cost += abs(total) + 1
            total = 1
        elif i % 2 == 0 and total >= 0:
            cost += abs(total) + 1
            total = -1

    ans = min(ans, cost)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

def main():
    n = int(input())
    a_list = list(map(int, input().split()))
    total1 = 0
    total2 = 0
    ans1 = 0
    ans2 = 0
    for i in range(n):
        total1 += a_list[i]
        if i % 2 != 0 and total1 <= 0:
            ans1 += abs(total1) + 1
            total1 = 1
        elif i % 2 == 0 and total1 >= 0:
            ans1 += total1 + 1
            total1 = -1
    for j in range(n):
        total2 += a_list[j]
        if j % 2 != 0 and total2 >= 0:
            ans2 += total2 + 1
            total2 = -1
        elif j % 2 == 0 and total2 <= 0:
            ans2 += abs(total2) + 1
            total2 = 1
    print(min(ans1, ans2))

            

if __name__ == '__main__':
    main()

Submission status: Accepted

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

def main():
    n = int(input())
    a_list = list(map(int, input().split()))
    total1 = 0
    total2 = 0
    ans1 = 0
    ans2 = 0
    for i in range(n):
        total1 += a_list[i]
        if i % 2 != 0 and total1 <= 0:
            ans1 += abs(total1) + 1
            total1 = 1
        elif i % 2 == 0 and total1 >= 0:
            ans1 += total1 + 1
            total1 = -1
    for j in range(n):
        total2 += a_list[j]
        if j % 2 != 0 and total2 >= 0:
            ans2 += total2 + 1
            total2 = -1
        elif j % 2 == 0 and total2 <= 0:
            ans2 += abs(total2) + 1
            total2 = 1
    print(min(ans1, ans2))
            

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import copy

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

def f1(a):
    memo = 0
    count = 0
    for i in range(n):
        if i % 2 == 0:
            if a[i] <= 0:
                count += 1 - a[i]
                memo = 1 - a[i]
        else:
            if a[i] >= 0:
                count += a[i] + 1
                memo = -(a[i] + 1)
        if i + 1 < n:
            a[i + 1] = a[i + 1] + a[i] + memo
            memo = 0
    else:
        return count

def f2(a):
    memo = 0
    count = 0
    for i in range(n):
        if i % 2 == 0:
            if a[i] >= 0:
                count += a[i] + 1
                memo = -(a[i] + 1)
        else:
            if a[i] <= 0:
                count += 1 - a[i]
                memo = 1 - a[i]
        if i + 1 < n:
            a[i + 1] = a[i + 1] + a[i] + memo
            memo = 0
    else:
        return count


print(min(f1(a), f2(b)))

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin

def li(): return [int(x) for x in stdin.readline().split()]
def li_(): return [int(x)-1 for x in stdin.readline().split()]
def lf(): return [float(x) for x in stdin.readline().split()]
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(ns())
def nf(): return float(ns())

n = ni()
a = li()

# 正→負→正→...
cur = a[0]
ans_pn = 0
if cur <= 0:
    ans_pn = abs(a[0])+1
    cur = 1

for i in range(1,n):
    cur += a[i]
    if i%2 == 0 and cur <= 0:
        ans_pn += abs(cur)+1
        cur = 1
    elif i%2 == 1 and cur >= 0:
        ans_pn += abs(cur)+1
        cur = -1


# 負→正→負...
cur = a[0]
ans_np = 0
if cur >= 0:
    ans_np = abs(a[0])+1
    cur = -1

for i in range(1,n):
    cur += a[i]
    if i%2 == 0 and cur >= 0:
        ans_np += abs(cur)+1
        cur = -1
    elif i%2 == 1 and cur <= 0:
        ans_np += abs(cur)+1
        cur = 1
        

print(min(ans_np, ans_pn))

Submission status: Accepted

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

a1 = now = 0
for i in range(N):
    now += src[i]
    if i%2:
        if now < 1:
            a1 += 1 - now
            now = 1
    else:
        if now > -1:
            a1 += now + 1
            now = -1
a2 = now = 0
for i in range(N):
    now += src[i]
    if i%2==0:
        if now < 1:
            a2 += 1 - now
            now = 1
    else:
        if now > -1:
            a2 += now + 1
            now = -1

print(min(a1,a2))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Sep  8 15:51:53 2018

@author: maezawa
"""

def sign(x):
    return x//abs(x)

def f(n, a0, s):
    cnt = 0
    cum = 0
    for i, ai in enumerate(a):
        cum += ai
        if cum == 0:
            cnt += 1
            cum = (-1)**i*s
        elif sign(cum) == (-1)**i*s:
            continue
        else:
            cnt += abs(cum)+1
            cum = (-1)**i*s
    return cnt

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

cnt = 0
cnt0 = f(n, a, -1)
cnt1 = f(n, a, 1)
cnt = min([cnt0,cnt1])
print(cnt)

Submission status: Accepted

Solution code:
N = int(input())

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

S = [0] * (N+1)

for i in range(N):
  S[i+1] = S[i] + A[i]
#print(S)
#S[1] > 0
ans1 = 0
work = 0
for i in range(1,N+1):
  if i%2 == 1:
    # pos is required
    if S[i] + work <= 0:
      temp = 1 - (S[i] + work)
      ans1 += temp
      work += temp
  else:
    # neg is required
    if S[i] + work >= 0:
      temp = (S[i] + work) + 1
      ans1 += temp
      work -= temp

#S[1] < 0
ans2 = 0
work = 0
for i in range(1,N+1):
  if i%2 == 1:
    # neg is required
    if S[i] + work >= 0:
      temp = (S[i] + work) + 1
      ans2 += temp
      work -= temp
  else:
    # neg is required
    if S[i] + work <= 0:
      temp = 1 - (S[i] + work)
      ans2 += temp
      work += temp

print(min(ans1, ans2))

Submission status: Accepted

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

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

ans1 = 0
sum1 = 0
sign1 = 1
for a in A:
    sum1 += a
    if sign1 == 1:
        ans1 += max(0, 1-sum1)
        sum1 += max(0, 1-sum1)
    else:
        ans1 += -min(0, -1-sum1)
        sum1 += min(0, -1-sum1)
    sign1 *= -1

ans2 = 0
sum2 = 0
sign2 = -1
for a in A:
    sum2 += a
    if sign2 == 1:
        ans2 += max(0, 1-sum2)
        sum2 += max(0, 1 - sum2)
    else:
        ans2 += -min(0, -1-sum2)
        sum2 += min(0, -1 - sum2)
    sign2 *= -1

print(min(ans1, ans2))

Submission status: Accepted

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

sum_now=a[0]
sum_before=-a[0]
if sum_before==0:
    sum_now=a[1]/abs(a[1])
    sum_before=-sum_now
    count_2+=1
else:
    count_2+=abs(int(sum_now))+1
    sum_now=-sum_now/abs(sum_now)
    sum_before=-sum_now
for i in range(n):
    if sum_now*sum_before>=0:
        if sum_before==0:
            sum_now=a[1]/abs(a[1])
            count_2+=1
        else:
            count_2+=abs(int(sum_now))+1
            sum_now=-sum_before/abs(sum_before)
    if i!=n-1:
        sum_before=sum_now
        sum_now=sum_now+a[i+1]
print(min(count_1, count_2))

Submission status: Accepted

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

@functools.lru_cache()
def memo(n):
    ans1 = 0
    ans2 = 0
    now = 0

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

    now = 0

    for i in range(n):
        now += a[i]
        if i % 2 == 1:
            if now <= 0:
                ans2 += 1 - now
                now = 1
        else:
            if now >= 0:
                ans2 += now + 1
                now = -1
    
    return min([ans1,ans2])

print(memo(n))

Submission status: Accepted

Solution code:
import itertools
n = int(input())
a = list(map(int,input().split()))
#'+-+-...'と'-+-+...'でそれぞれ求める
res1 = 0
res2 = 0
dif1 = 0
dif2 = 0
for i,j in enumerate(itertools.accumulate(a)):
    s = j + dif1
    t = j + dif2
    if i%2==0:
        if s<1:
            dif1 += 1 - s
            res1 += 1 - s
        if t>-1:
            dif2 -= 1 + t
            res2 += 1 + t
    else:
        if s>-1:
            dif1 -= 1 + s
            res1 += 1 + s
        if t<1:
            dif2 += 1 - t
            res2 += 1 - t
print(min(res1,res2))

Submission status: Accepted

Solution code:
import itertools
n = int(input())
a = list(map(int,input().split()))
sum = list(itertools.accumulate(a))
#'+-+-...'と'-+-+...'でそれぞれ求める
res1 = 0
res2 = 0
dif1 = 0
dif2 = 0
for i in range(n):
    s = sum[i] + dif1
    t = sum[i] + dif2
    if i%2==0:
        if s<1:
            dif1 += 1 - s
            res1 += 1 - s
        if t>-1:
            dif2 -= 1 + t
            res2 += 1 + t
    else:
        if s>-1:
            dif1 -= 1 + s
            res1 += 1 + s
        if t<1:
            dif2 += 1 - t
            res2 += 1 - t
    #print(dif1,res1,dif2,res2)
print(min(res1,res2))
#print(res1,res2)

Submission status: Accepted

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

s=0
c=0
for (i,j) in enumerate(l):
  if i%2: #plus
    if s+j<=0:
      c+=(abs(s+j)+1)
      s=1
    else:
      s+=j
  else: #minus
    if s+j>=0:
      c+=(abs(s+j)+1)
      s=-1
    else:
      s+=j
a=c

s=0
c=0
for (i,j) in enumerate(l):
  if i%2==0: #plus
    if s+j<=0:
      c+=(abs(s+j)+1)
      s=1
    else:
      s+=j
  else: #minus
    if s+j>=0:
      c+=(abs(s+j)+1)
      s=-1
    else:
      s+=j
b=c
print(min(a,b))

Submission status: Accepted

Solution code:
import numpy as np

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

def calc(a):
    value = a[0]
    sign = value >= 0
    result = 0
    for i in a[1:]:
        value += i
        diff = 0
        if sign and value >= 0:
            diff = value + 1
        elif not sign and value < 0:
            diff = value - 1
        result += abs(diff)
        sign = not sign
        value -= diff
        if value == 0:
            diff += sign
            value += diff
            result += diff
    return result

if a[0] == 0:
    a[0] = 1
    r1 = calc(a[:])
    a[0] = -1
    r2 = calc(a[:])
    print(min(r1, r2) + 1)
else:
    r1 = calc(a[:])
    diff = -a[0] - a[0] // abs(a[0])
    a[0] += diff
    r2 = calc(a[:]) + abs(diff)
    print(min(r1, r2))

Submission status: Accepted

Solution code:
n = int(input())
a = [int(_) for _ in input().split()]
new_a_plus = [a[i] for i in range(n)]
new_a_minus = [a[i] for i in range(n)]

count_plus = 0
now_total_plus = 0

for i in range(0, n):
    if i % 2 == 0:
        if now_total_plus + a[i] <= 0:
            new_a_plus[i] = - now_total_plus + 1
            count_plus += new_a_plus[i] - a[i]
    else:
        if now_total_plus + a[i] >= 0:
            new_a_plus[i] = - now_total_plus - 1
            count_plus += a[i] - new_a_plus[i]
    now_total_plus += new_a_plus[i]

count_minus = 0
now_total_minus = 0

for i in range(0, n):
    if i % 2 == 0:
        if now_total_minus + a[i] >= 0:
            new_a_minus[i] = - now_total_minus - 1
            count_minus += a[i] - new_a_minus[i]
    else:
        if now_total_minus + a[i] <= 0:
            new_a_minus[i] = - now_total_minus + 1
            count_minus += new_a_minus[i] - a[i]
    now_total_minus += new_a_minus[i]

print(min(count_plus, count_minus))

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
def f(a, b):
    # b == 0: １番めが正

    sum_a = 0
    cost = 0
    for i, ai in enumerate(a):
        if i % 2 == b:
            sum_a += ai
            if sum_a <= 0:
                x = 1 - sum_a
                sum_a += x
                cost += abs(x)
        else:
            sum_a += ai
            if sum_a >= 0:
                x = -1 - sum_a
                sum_a += x
                cost += abs(x)
    return cost
print(min(f(a, 0), f(a, 1)))

Submission status: Accepted

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

answers = []
for p in [True, False]:
    ans = 0
    cumsum = 0
    for i in range(n):
        if p:
            if cumsum+a[i] >= 0:
                ans += cumsum+a[i]+1
                cumsum = -1
            else:
                cumsum += a[i]
            p = False
        else:
            if cumsum+a[i] <= 0:
                ans += 1-(cumsum+a[i])
                cumsum = 1
            else:
                cumsum += a[i]
            p = True
        # print(cumsum)
    answers.append(ans)
    
print(min(answers))

Submission status: Accepted

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

ans = float('inf')
for sgn in [1, -1]:
    s = 0
    cnt = 0
    for i in range(n):
        s += a[i]
        if s * sgn > 0:
            pass
        else:
            #s <= 0 and sgn = 1
            #s >= 0 and sgn = -1
            cnt += abs(sgn - s)
            s = sgn
        sgn *= (-1)
    ans = min(ans, cnt)
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
import sys,heapq,bisect,math,itertools,string
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
AtoZ = [chr(i) for i in range(65,65+26)]
atoz = [chr(i) for i in range(97,97+26)]

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

flag = True
ans1 = ans2 = 0
sum1 = sum2 = 0

for i in range(N):
	sum1 += aa[i]
	sum2 += aa[i]
	if flag:
		if sum1 <= 0:
			ans1 += 1 - sum1
			sum1 = 1
		if sum2 >= 0:
			ans2 += sum2 - (-1)
			sum2 = -1
		flag = False
	else:
		if sum1 >= 0:
			ans1 += sum1 - (-1)
			sum1 = -1
		if sum2 <= 0:
			ans2 += 1 - sum2
			sum2 = 1
		flag = True

print(min(ans1,ans2))

Submission status: Accepted

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


def solve(isPosi,N,A):
    ans = 0
    sm = 0
   
    for a in A:
        if isPosi:
            sm += a
            if sm >= 0:
                ans += abs(-1-sm)
                sm = -1
            isPosi = False
        
        else:
            sm += a
            if sm <= 0:
                ans += abs(1-sm)
                sm = 1
            isPosi = True
        
    return ans

ans_p = solve(True,N,A)
ans_n = solve(False,N,A)

print(min(ans_p,ans_n))

Submission status: Accepted

Solution code:
def count_op(n, a):
    i_sum = a[0]
    op_num = 0
    for i in range(1, n):
        tmp_sum = i_sum + a[i]
        if i_sum > 0:
            if tmp_sum == 0:
                op_num += 1
                a[i] -= 1
                tmp_sum -= 1
            elif tmp_sum > 0:
                op_num += tmp_sum + 1
                a[i] -= tmp_sum + 1
                tmp_sum = -1
        else:
            if tmp_sum == 0:
                op_num += 1
                a[i] += 1
                tmp_sum += 1
            elif tmp_sum < 0:
                op_num += -tmp_sum + 1
                a[i] += -tmp_sum + 1
                tmp_sum = 1
        i_sum = tmp_sum
    return op_num

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

if a[0] != 0:
    b = a[:]
    a_num = count_op(n, a)
    b_num = 0
    if b[0] > 0:
        b_num += b[0] + 1
        b[0] = -1
    else:
        b_num += -b[0] + 1
        b[0] = 1
    b_num += count_op(n, b)
    print(min(a_num, b_num))
else:
    b = a[:]
    a[0] = 1
    a_num = count_op(n, a) + 1
    b[0] = -1
    b_num = count_op(n, b) + 1
    print(min(a_num, b_num))

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
#case1
i = 0
su = 0
cost1 = 0
while i < N:
  if i%2==0 and su+A[i]>0:
    su = su+A[i]
  elif i%2==1 and su+A[i]<0:
    su = su+A[i]
  elif i%2==0 and su+A[i]<=0:
    cost1 += 1-(su+A[i])
    su = 1
  elif i%2==1 and su+A[i]>=0:
    cost1 += 1+(su+A[i])
    su = -1  
  i += 1
#case2
i = 0
su = 0
cost2 = 0
while i < N:
  if i%2==0 and su+A[i]<0:
    su = su+A[i]
  elif i%2==1 and su+A[i]>0:
    su = su+A[i]
  elif i%2==0 and su+A[i]>=0:
    cost2 += 1+(su+A[i])
    su = -1
  elif i%2==1 and su+A[i]<=0:
    cost2 += 1-(su+A[i])
    su = 1 
  i += 1

print(min(cost1,cost2))