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

    S = list(input())
    checklist = [0 for i in range(26)]
    for i in S:
        checklist[ord(i) - ord("a")] += 1
    ans = True

    for i in checklist:
        if i > 1:
            ans = False

    if not ans:
        print(-1)
        return 0
    else:
        ans = False
        for i in range(len(checklist)):
            if checklist[i] == 0:
                for i in S:
                    print(i, end="")
                print(chr(i + ord("a")), end = "")
                print()
                ans = True
                break

        if not ans:
            new_S = []
            for i in S:
                new_S.append(ord(i))

            for i in range(len(new_S) - 1):
                if new_S[i] > new_S[i + 1]:
                    for j in range(i - 1):
                        print(S[j], end = "")
                    print(chr(new_S[i - 1] + 1), end = "")
                    print()
                    ans = True
                    break

            if not ans:
                print(-1)
#main()

def ABC069D():

    H, W = map(int, input().split())
    N = int(input())
    a = list(map(int, input().split()))
    ans = []
    for i in range(N):
        for j in range(a[i]):
            ans.append(i + 1)
    printlist = [[0 for i in range(W)] for j in range(H)]
    k = 0
    for i in range(H):
        for j in range(W):
            printlist[i][j] = ans[k]
            k += 1
        if i % 2 != 0:
            printlist[i] = printlist[i][::-1]

    for i in range(H):
        for j in range(W):
            print(printlist[i][j], end = "")
            if j != W:
                print(" ", end = "")
        print()
    print()
#ABC069D()

import math
def cc(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

def ABC057D():

    N, A, B = map(int, input().split())
    v = list(map(int, input().split()))
    v = sorted(v)[::-1]

    anslist = []
    for i in range(A, B + 1):

        anslist.append([sum(v[0:i]) / i, i, v[i - 1]])
    anslist.sort()
    anslist = anslist[::-1]
    ans = anslist[0][0]
    key = anslist[0][2]
    long = anslist[0][1]
    print(ans)
    for i in range(1, len(anslist)):
        if anslist[i][0] == anslist[i - 1][0]:
            ans = anslist[i][0]
            key = anslist[i][2]
            long = anslist[i][1]
        else:
            break
    #print(anslist)
    #print(ans, key, long)
    cnt = 0
    for i in v:
        if i == key:
            cnt += 1

    c = 0
    for i in v[:long]:
        #print(i)
        if i == key:
            c += 1
    #print(c, long)
    ans = 0
    if c == long:
        for i in range(A,  min(B + 1, cnt + 1)):
            ans += cc(cnt, i)
    else:
        ans = cc(cnt, c)
    #print(anslist)
    #print(cnt, c, long)
    print(ans)
#ABC057D()

def ABC104D():
    S = list(input())
    A_cnt = 0
    B_cnt = 0
    C_cnt = 0
    Q_cnt = 0
    ans = 0
    for i in S:
        if i == "A":
            A_cnt += 1
        elif i == "B":
            B_cnt += 1
        elif i == "C":
            C_cnt += 1
        else:
            Q_cnt += 1
    for i in range(Q_cnt + 1):
        for j in range(Q_cnt - i + 1):
            k = Q_cnt - i - j
            if A_cnt + i > 0 and B_cnt + j > 0 and C_cnt + k > 0:
                f_i = math.factorial(i)
                f_j = math.factorial(j)
                f_k = math.factorial(k)
                if f_i == 0:
                    f_i = 1
                if f_j == 0:
                    f_j = 1
                if f_k == 0:
                    f_k = 1
                ans += (A_cnt + i) * (B_cnt + j) * (C_cnt + k) * math.factorial(Q_cnt) // f_i // f_j // f_k
                print(ans, i, j, k, A_cnt + i, B_cnt + j, C_cnt + k)
                print(math.factorial(Q_cnt), f_i, f_j, f_k)
    print(ans)
#ABC104D()

def ARC082D():
    N = int(input())
    p = list(map(int, input().split()))
    cnt = 0
    if p[N - 1] == N:
        #print(p[N - 1], N)
        p[-2], p[-1] = p[-1], p[-2]
        cnt += 1

    for i in range(N - 1):
        if p[i] == i + 1:
            p[i], p[i + 1] = p[i + 1], p[i]
            cnt += 1
    print(cnt)
#ARC082D()

from queue import Queue
def ABC070D():
    N = int(input())
    a, b, c =map(int, input().split())
    Q, K = map(int, input().split())
    xy = [list(map(int, input().split())) for i in range(Q)]
    x = [[] for i in range(N)]
    for i, j in xy:
        x[i - 1].append(j - 1)
        x[j - 1].append(i - 1)

    q = Queue()
    visited = [0 for i in range(N)]

def ABC076D():
    N = int(input())
    t = list(map(int, input().split()))
    v = list(map(int, input().split()))
    speed_lim = [0]
    speed_list = [0 for i in range(sum(t) + 1)]
    for i in range(N):
        for j in range(t[i]):
            speed_lim.append(v[i])
    print(speed_lim)
    for i in range(1, sum(t) + 1):
        speed_list[i] = speed_list[i - 1] + 1
        if speed_list[i] > speed_lim[i]:
            speed_list[i] = speed_lim[i]
    print(speed_list)
    speed_list[-1] = 0
    for i in range(sum(t) - 1, -1, -1):
        speed_list[i] = min(speed_list[i + 1] + 1, speed_list[i])
        if speed_list[i] > speed_lim[i + 1]:
            speed_list[i] = speed_lim[i + 1]
    print(speed_list)
    ans = 0
    for i in speed_list:
        ans += i

    print(ans)
#ABC076D()

def ABC085D():
    N, H = map(int, input().split())
    ab = [list(map(int, input().split())) for i in range(N)]
    a = []
    b = []
    for i, j in ab:
        a.append(i)
        b.append(j)
    a.sort()
    b.sort()
    a = a[::-1]
    b = b[::-1]
    damage = 0
    cnt = 0
    for i in b:
        if i < a[0]:
            break
        damage += i
        cnt += 1
        if damage >= H:
            break
    key = 0
    if damage < H:
        key = (H - damage) / a[0]
        if int(key) != key:
            key += 1
        key = int(key)

    cnt += key

    print(cnt)
#ABC085D()

def ARC068D():
    N = int(input())
    A = list(map(int, input().split()))
    A.sort()
    count_list = []
    cnt = 1
    #print(A)
    for i in range(1, N):
        if A[i] == A[i - 1]:
            cnt += 1
        else:
            count_list.append(cnt)
            cnt = 1
    count_list.append(cnt)
    ans_cnt = 0
    #print(count_list)
    for i in range(len(count_list)):
        if count_list[i] > 2:
            ans_cnt += (count_list[i] % 2) - 1
            count_list[i] %= 2
            if count_list[i] == 0:
                count_list[i] = 2
    #print(ans_cnt)
    count_list = sorted(count_list)[::-1]
    for i in range(len(count_list) - 1):
        if count_list[i] == 2 and count_list[i + 1] == 2:
            ans_cnt += 1
            count_list[i] = 1
            count_list[i + 1] = 1
    count_list = sorted(count_list)[::-1]
    if count_list[0] == 2:
        count_list[0] = 0
    #print(ans_cnt)
    #print(count_list)
    print(sum(count_list))
#ARC068D()

def ARC073D():
    N, W = map(int, input().split())
    wv = [list(map(int, input().split())) for i in range(N)]
    wv.sort()
    count_list = []
    cnt = 1
    weight_list = []
    s = 0
    g = 0
    for i in range(N - 1):
        if wv[i][0] != wv[i + 1][0]:
            g = i
            count_list.append(cnt)
            weight_list.append([wv[i][0], s, g, cnt])
            s = i + 1
            g = i + 1
            cnt = 1
        else:
            g = i
            cnt += 1

    count_list.append(cnt)
    weight_list.append([wv[-1][0], s, g, cnt])
    print(weight_list)
    wl = []
    for i in weight_list:
        this_weight = i[0]
        this_list = []
        for j in wv[i[1]:i[2] + 1]:
            this_list.append(j[1])
        this_list = sorted(this_list)[::-1]
        print(this_list)
        wl.append([this_weight, this_list])

def ARC081D():
    pattern = []
    N = int(input())
    S1 = list(input())
    S2 = list(input())
    i = 0
    while i < N:
        if S1[i] == S2[i]:
            pattern.append("X")
        else:
            pattern.append("Y")
            i += 1
        i += 1
    ans_list = []
    for i in range(len(pattern)):
        if i == 0:
            if pattern[i] == "X":
                ans_list.append(3)
            else:
                ans_list.append(6)
        else:
            if pattern[i] == "X":
                if pattern[i - 1] == "X":
                    ans_list.append(2)
                else:
                    ans_list.append(1)
            elif pattern[i] == "Y":
                if pattern[i - 1] == "X":
                    ans_list.append(2)
                elif pattern[i - 1] == "Y":
                    ans_list.append(3)
    #print(pattern)
    #print(ans_list)
    ans = 1
    for i in ans_list:
        ans *= i
    print(ans % (1000000007))
#ARC081D()

def ARC090D():
    N, M = map(int, input().split())
    LRD = [list(map(int, input().split())) for i in range(M)]
    L = []
    R = []
    D = []
    LRD.sort()
    root = [[] for i in range(N)]
    for i, j, k in LRD:
        L.append(i)
        R.append(j)
        D.append(k)
        root[i - 1].append(j - 1)
    print(root)
#ARC090D()

def ABC073D():
    N, M, R = map(int, input().split())
    r = list(map(int, input().split()))
    ABC = [list(map(int, input().split())) for i in range(M)]
    root = [[1000000000 for i in range(N)] for j in range(N)]
    for i, j, k in ABC:
        root[i - 1][j - 1] = k
        root[j - 1][i - 1] = k

    import itertools
    def kumiawase(list_name):  # list_name(リスト)のすべての並び替え
        return itertools.permutations(list_name)

    #for i in range(N):
     #   for j in range(N):
      #      for k in range(N):
       #         if root[i][j] > root[i][k] + root[k][j]:
        #            root[i][j] = root[i][k] + root[k][j]

    for i in range(N):
        for j in range(N):
            for k in range(N):
                if root[N - i - 1][N - j - 1] > root[N - i - 1][N - k - 1] + root[N - k - 1][N - j - 1]:
                    root[N - i - 1][N - j - 1] = root[N - i - 1][N - k - 1] + root[N - k- 1][N - j - 1]

    a = kumiawase(r)
    ans = float("inf")
    for i in a:
        key = 0
        for j in range(len(i) - 1):
            key += root[i[j] - 1][i[j + 1] - 1]
        if ans > key:
            ans = int(key)
    #print(root)
    print(ans)
#ABC073D()

def ARC061D():
    H, W, N = map(int, input().split())
    ab = [list(map(int, input().split())) for i in range(N)]
    ab.sort()
    tmp_list = []
    ans_list = [0 for i in range(10)]
    for x, y, in ab:
        for i in range(x - 3, x):
            for j in range(y - 3, y):
                if 0 <= i < H - 2 and 0 <= j < W - 2:
                    #print(x, y, i, j)
                    tmp_list.append([i, j])
    #print(tmp_list)
    tmp_list.sort()
    temp = 1
    #print(tmp_list)
    cnt = 0
    for i in range(1, len(tmp_list) + 1):
        if i != len(tmp_list):
            if tmp_list[i] == tmp_list[i - 1]:
                temp += 1
            else:
                ans_list[temp] += 1
                temp = 1
                cnt += 1
        else:
            ans_list[temp] += 1
            cnt += 1
    #print(ans_list)

    key = 0
    for i in range(len(ans_list)):
        key += i * ans_list[i]
    ans_list[0] = (H - 2) * (W - 2) - cnt
    #print(key)
    #print((H - 2) * (W - 2) - key)

    for i in range(10):
        print(ans_list[i])
#ARC061D()

from scipy.sparse import csgraph
#root = csgraph.floyd_warshall(root)

def ABC079D():
    H, W = map(int, input().split())
    c = [list(map(int, input().split())) for i in range(10)]
    A = [list(map(int, input().split())) for i in range(H)]
    #c = csgraph.floyd_warshall(c, False)
    for k in range(10):
        for i in range(10):
            for j in range(10):
                c[i][j] = min(c[i][j], c[i][k] + c[k][j])
    #print(c)
    ans = 0
    for i in A:
        for j in i:
            if j != -1 and j != 1:
                ans += c[j][1]
                #print(c[j][1], j)
    print(int(ans))
#ABC079D()

import fractions
def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)

def AGC028A():
    N, M = map(int, input().split())
    S = input()
    T = input()

    key = lcm(N, M)
    n = key // N
    m = key // M
    n_list = []
    for i in range(0, key, n):
        n_list.append(i)
    m_list = []
    for j in range(0, key, m):
        m_list.append(j)

    #print(n_list, m_list)
    i = 0
    j = 0
    while True:
        if i >= len(n_list) or j >= len(m_list):
            break
        if i >= len(S) or j >= len(T):
            break
        if n_list[i] == m_list[j]:
            if S[i] != T[j]:
                print(-1)
                return 0
        if n_list[i] > m_list[j]:
            j += 1
        elif n_list[i] < m_list[j]:
            i += 1
        else:
            i += 1
            j += 1
    print(key)
#AGC028A()

import math
def AGC028B():
    N = int(input())

    A = list(map(int, input().split()))
    import copy
    a = copy.deepcopy(A)
    for i in range(1, N):
        A[i] += A[i - 1]
    ans = 0
    for i in range(1, N):
        key = A[i] * 2 - A[0] - (A[i] - A[i - 1])
        ans += math.factorial(N - i) * i * key
        #print(key)
    print(ans)
    A = copy.deepcopy(a[::-1])
    for i in range(1, N):
        A[i] += A[i - 1]
    print(A)
    for i in range(1, N):
        key = A[i] * 2 - A[0] - (A[i] - A[i - 1])
        ans += math.factorial(N - i) * i * key
        #print(key)
    ans += A[N - 1] * math.factorial(N - 1)

    print(ans)
#AGC028B()

def AGC028B2():
    N = int(input())

    A = list(map(int, input().split()))
    import copy
    a = copy.deepcopy(A)
    for i in range(1, N):
        A[i] += A[i - 1]
    ans = 0
    for i in range(1, N):
        A[i] = A[i] * (i + 1) - A[i - 1]
    for i in range(1, N):
        ans += math.factorial(N - i) * i * A[i - 1]

    print(ans)
    ans += A[N - 1] * N

    print(ans)
#AGC028B2()

def CF18QBA():
    N = int(input())
    print(100 - 100 // N)
#CF18QBA()

def CF18QBB():
    N, X = map(int, input().split())
    ab = [list(map(int, input().split())) for i in range(N)]
    key = ab[0][1]
    ans = 0
    for i, j in ab:
        if j > key:
            key = j
            key2 = i
        ans += i * j
    ans += key * X
    print(ans)
#CF18QBB()

def CF18QBC():
    N = int(input())
    ans_list = [[0 for i in range(N)] for j in range(N)]
    key1 = 1
    key2 = key1
    for i in range(N):
        #print(key2)
        for j in range(N):
            if key2 == j:
                ans_list[i][j] = 1
                key2 += 5
        if key1 == 1:
            key1 = 3
        elif key1 == 3:
            key1 = 0
        elif key1 == 0:
            key1 = 2
        elif key1 == 2:
            key1 = 4
        elif key1 == 4:
            key1 = 1
        key2 = key1
    cnt = 0
    for i in range(N):
        for j in range(N):
            OK = 0
            if i > 0:
                if ans_list[i - 1][j] == 1:
                    OK = 1
            if i < N - 1:
                if ans_list[i + 1][j] == 1:
                    OK = 1
            if j > 0:
                if ans_list[i][j - 1] == 1:
                    OK = 1
            if j < N - 1:
                if ans_list[i][j + 1] == 1:
                    OK = 1
            if OK == 0:
                #cnt += 1
                ans_list[i][j] = 1
                1

    for i in ans_list:
        for j in i:
            if j == 0:
                print(".", end = "")
            if j == 1:
                print("X", end = "")
                cnt += 1
        print()
#CF18QBC()

def CF18QBE():
    N = int(input())
    ans = 10000
    tmp_list = []
    key = 69720375229712477164533808935312303556800
    for i in range(1, N + 1):
        tmp_list.append([key // i, i])
    ans = tmp_list[0][0]
    cnt = 0
    ans_list = []
    ans_list.append(["+", 1])
    key = []
    while True:
        if ans < 1 / N:
            print(1)
            break
        if cnt >= 320:
            print(2)
            break
        #print(ans)
        #print(tmp_list)
        for i in range(len(tmp_list)):
            if tmp_list[i][0] < ans:
                key = tmp_list[i]
        if key:
            ans_list.append(["-", key[1]])
        if key:
            ans -= key[0]
        #print(ans)
        key = []
        cnt += 1
    #print(ans_list)
    print(len(ans_list))
    for i, j in ans_list:
        print(i, j)
#CF18QBE()

def niconicoB():
    N, C = map(int, input().split())
    L = [int(input()) for i in range(N)]
    L.sort()
    cnt = 0
    while len(L) > 0:
        if len(L) == 1:
            cnt += 1
            break
        if L[-1] + L[0] + 1 <= C:
            cnt += 1
            del L[0]
            del L[-1]
        else:
            cnt += 1
            del L[-1]
    print(cnt)
#niconicoB()

def ABC064D():
    N = int(input())
    S = list(input())
    cnt = 0
    start = 0
    for i in S:
        if i == "(":
            cnt += 1
        elif i == ")":
            cnt -= 1
        if cnt < 0:
            start += 1
            cnt += 1
    tmp = []
    for i in range(start):
        tmp.append("(")
    S = tmp + S
    cnt_start = 0
    cnt_end = 0
    for i in S:
        if i == "(":
            cnt_start += 1
        elif i == ")":
            cnt_end += 1
    tmp = []
    for i in range(cnt_start - cnt_end):
        tmp.append(")")
    S = S + tmp

    for i in S:
        print(i, end = "")
    print()
#ABC064D()

from operator import itemgetter

def ARC072C():
    N = int(input())
    a = list(map(int, input().split()))
    cnt1 = 0
    cnt2 = 0
    sum1 = a[0]
    sum2 = a[0]
    if sum1 <= 0:
        cnt1 = 1 - a[0]
        sum1 = 1
    if sum2 >= 0:
        cnt2 = abs(-1 - a[0])
        sum2 = -1
    j = 1
    #print(sum1, sum2)
    for i in range(1, N):
        sum1 += a[i]
        sum2 += a[i]
        if j % 2 == 0:
            if sum1 <= 0:
                cnt1 += 1 - sum1
                sum1 = 1
            if sum2 >= 0:
                cnt2 += abs(-1 - sum2)
                sum2 = -1
        else:
            if sum1 >= 0:
                cnt1 += abs(-1 - sum1)
                sum1 = -1
            if sum2 <= 0:
                cnt2 += 1 - sum2
                sum2 = 1
        j += 1
        #print(sum1, sum2)
    #print(cnt1, cnt2)
    print(min(cnt1, cnt2))
ARC072C()

Submission status: Accepted

Solution code:
def ARC072C():
    N = int(input())
    a = list(map(int, input().split()))
    cnt1 = 0
    cnt2 = 0
    sum1 = a[0]
    sum2 = a[0]
    if sum1 <= 0:
        cnt1 = 1 - a[0]
        sum1 = 1
    if sum2 >= 0:
        cnt2 = abs(-1 - a[0])
        sum2 = -1
    j = 1
    #print(sum1, sum2)
    for i in range(1, N):
        sum1 += a[i]
        sum2 += a[i]
        if j % 2 == 0:
            if sum1 <= 0:
                cnt1 += 1 - sum1
                sum1 = 1
            if sum2 >= 0:
                cnt2 += abs(-1 - sum2)
                sum2 = -1
        else:
            if sum1 >= 0:
                cnt1 += abs(-1 - sum1)
                sum1 = -1
            if sum2 <= 0:
                cnt2 += 1 - sum2
                sum2 = 1
        j += 1
        #print(sum1, sum2)
    #print(cnt1, cnt2)
    print(min(cnt1, cnt2))
ARC072C()

Submission status: Accepted

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

flag = 1
temp_1 = 0
temp = 0
for i in range(n):
    temp += a[i]
    if flag * temp <= 0:
        temp_1 += 1 - flag * temp
        temp = flag
    flag *= -1

flag = -1
temp_2 = 0
temp = 0
for i in range(n):
    temp += a[i]
    if flag * temp <= 0:
        temp_2 += 1 - flag * temp
        temp = flag
    flag *= -1

print(min(temp_1, temp_2))

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
ans1 = 0
s = 0
for i, v in enumerate(a):
    if i % 2 and s + v >= 0:
        ans1 += abs(-1 - s - v)
        s = -1
    elif i % 2 == 0 and s + v <= 0:
        ans1 += abs(1 - s - v)
        s = 1
    else:
        s += v

s = 0
ans2 = 0
for i, v in enumerate(a):
    if i % 2 and s + v <= 0:
        ans2 += abs(1 - s - v)
        s = 1
    elif i % 2 == 0 and s + v >= 0:
        ans2 += abs(-1 - s - v)
        s = -1
    else:
        s += v

print(min(ans1, ans2))

Submission status: Accepted

Solution code:
def osilate(seq):
    flag = 1
    acc = 0
    ans = 0
    #while loop O(n)
    for i in range(len(seq)):
        a = seq[i]
        acc += a
        flag = i%2

        if flag == 0:
            if acc <= 0:
                ans += 1-acc
                acc = 1
        if flag == 1:
            if acc >= 0:
                ans += 1+acc
                acc = -1
        #print(seq, acc, acc)
        flag = flag * (-1)
    return ans

n = int(input()) #(1)
seq = [int(i) for i in input().split()] #O(N)

seq_rev = [-i for i in seq]  # O(N)
print(min(osilate(seq),osilate(seq_rev))) #O(2N)

Submission status: Accepted

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

Submission status: Accepted

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

ans2 = abs(a[0]) + 1
if a[0] == 0:
    ans2 = 1
    tmp = -1
else:
    ans2 = abs(a[0]) + 1
    tmp = -a[0] // abs(a[0])
is_plus = tmp > 0
for i in range(1, n):
    tmp += a[i]
    if is_plus == (tmp > 0):
        ans2 += abs(tmp) + 1
        if is_plus:
            tmp = -1
        else:
            tmp = 1
        is_plus = tmp > 0
    else:
        is_plus = tmp > 0

print(min(ans1, ans2))

Submission status: Accepted

Solution code:
N=int(input())
A=[int(i) for i in input().split()]
ans=0
#i%2が正
s=0
for i in range(N):
    s+=A[i]
    if i%2==0:
        if s<=0:
            ans+=1-s
            s=1
    else:
        if s>=0:
            ans+=s+1
            s=-1
    #print(s,ans)
nums=0
s=0
for i in range(N):
    s+=A[i]
    if i%2!=0:
        if s<=0:
            nums+=1-s
            s=1
    else:
        if s>=0:
            nums+=s+1
            s=-1
    #print(s,nums)
print(min(nums,ans))

Submission status: Accepted

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

Submission status: Accepted

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

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

ret = [0,0]
sum = [0,0]

if a[0]==0:
    sum[0] = 1
    ret[0] = 1
    sum[1] = -1
    ret[1] = 1
elif a[0]>0:
    sum[0] = a[0]
    sum[1] = -1
    ret[1] = a[0]+1
else:
    sum[0] = 1
    ret[0] = -1*a[0]+1
    sum[1] = a[0]

for i in range(1,n):
    for j in range(2):
        if sum[j]*(sum[j]+a[i])<0:
            sum[j] += a[i]
        elif sum[j]+a[i]==0:
            if sum[j]>0:
                sum[j] = -1
            else:
                sum[j] = 1
            ret[j] += 1
        elif sum[j]+a[i]>0:
            ret[j] += sum[j]+a[i]+1
            sum[j] = -1
        else:
            ret[j] += -1*(sum[j]+a[i])+1
            sum[j] = 1

print(min(ret[0],ret[1]))

Submission status: Accepted

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

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

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

print(result)

Submission status: Accepted

Solution code:
import numpy as np
n = int(input())

arr = map(int,raw_input().split())

cs = np.cumsum(arr)

to = [1,-1]

def digit(n):
	if n > 0:
		return 1
	elif n < 0:
		return -1
	else :
		return 0

tmp1 = 0
ans1 = 0
p = 0
for i in range(n):
	x = cs[i] + tmp1
	if digit(x) != to[p]:
		tmp1 += to[p] - x
		ans1 += abs(to[p] - x)

	p = (p+1)%2

tmp2 = 0
ans2 = 0
p = 1
for i in range(n):
	x = cs[i] + tmp2
	if digit(x) != to[p]:
		tmp2 += to[p] - x
		ans2 += abs(to[p] - x)
	p = (p+1) %2


print min(ans1,ans2)

Submission status: Accepted

Solution code:
n = int(input())

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

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

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
b = a[:]
cnt1, cnt2 = 0, 0
s = 0
for i in range(n):
  if (i%2==0 and s+a[i]<=0) or (i%2==1 and s+a[i]>=0) :
    cnt1 += abs(s+a[i])+1
    if i%2:
      s = -1
    else:
      s = 1
  else:
    s += a[i]
s = 0
for i in range(n):
  if (i%2==1 and s+a[i]<=0) or (i%2==0 and s+a[i]>=0) :
    cnt2 += abs(s+a[i])+1
    if i%2:
      s = 1
    else:
      s = -1
  else:
    s += a[i]
print(min(cnt1, cnt2))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys, math, copy
# import fractions, itertools
# import numpy as np
# import scipy
# sys.setrecursionlimit(1000000)

HUGE = 2147483647
HUGEL = 9223372036854775807
ABC = "abcdefghijklmnopqrstuvwxyz"

def next(su, ai, sign):
    assert sign in [-1, 1]
    if (su + ai) * sign > 0:
        return ai
    else:
        nextsu = sign
        nextai = nextsu - su
        return nextai

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

    ress = HUGEL
    for beg in [-1, 1]:
        res = 0
        su = 0
        sign = beg
        for i in range(n):
            ai = next(su, an[i], sign)
            su = su + ai
            res += abs(ai - an[i])
            sign *= (-1)
        ress = min(ress, res)

    print(ress)

main()

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
N = int(input())

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

if A[0]==0:
    B = [1,-1]
    ANS = [1,1]
else:
    B = [A[0],(-1)*(A[0])//abs(A[0])]
    ANS = [0,abs(A[0])+1]

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

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
ans = 0
ans2 = 0
a_sum = 0
b_sum = 0

if a[0] < 0:
	a = [-a[i] for i in range(n)]

b = list.copy(a)

if a[0] == 0:
	a[0] = 1
	ans += 1

a_sum += a[0]

for i in range(1, n, 2):
	if a_sum + a[i] >= 0:
		ans += a_sum + a[i] + 1
		a[i] = -1 - a_sum
	a_sum += a[i]
	if i == n - 1:
		break
	if a_sum + a[i + 1] <= 0:
		ans += 1 - a_sum - a[i + 1]
		a[i + 1] = 1 - a_sum
	a_sum += a[i + 1]

if b[0] == 0:
	b[0] = -1
	ans2 += 1
else:
	ans2 += b[0] + 1
	b[0] = -1

b_sum += b[0]

for i in range(1, n, 2):
	if b_sum + b[i] <= 0:
		ans2 += 1 - b_sum - b[i]
		b[i] = 1 - b_sum
	b_sum += b[i]
	if i == n - 1:
		break
	if b_sum + b[i + 1] >= 0:
		ans2 += b_sum + b[i + 1] + 1
		b[i + 1] = -1 - b_sum
	b_sum += b[i + 1]

print(min(ans, ans2))

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
n = int(input())
l = list(map(int, input().split()))
even = 0
e_sum = 0
odd = 0
o_sum = 0
for i in range(n):
  e_sum += l[i]
  if i % 2 == 0 and e_sum <= 0:
    even += abs(e_sum)+1
    e_sum = 1
  elif not i % 2 == 0 and e_sum >= 0:
    even += abs(e_sum)+1
    e_sum = -1

for i in range(n):
  o_sum += l[i]
  if i % 2 == 0 and o_sum >= 0:
    odd += abs(o_sum)+1
    o_sum = -1
  elif not i % 2 == 0 and o_sum <= 0:
    odd += abs(o_sum)+1
    o_sum = 1

print(min(even, odd))

Submission status: Accepted

Solution code:
n = int(input())
l = list(map(int, input().split()))
now = l[0]

oddSum = 0
oddOp = 0
for i in range(n):
  oddSum += l[i]
  if not i % 2 == 0 and oddSum <= 0:
    oddOp += abs(oddSum) + 1
    oddSum = 1
  elif i % 2 == 0 and oddSum >= 0:
    oddOp += abs(oddSum) + 1
    oddSum = -1

evenSum = 0
evenOp = 0
for i in range(n):
  evenSum += l[i]
  if i % 2 == 0 and evenSum <= 0:
    evenOp += abs(evenSum) + 1
    evenSum = 1
  elif not i % 2 == 0 and evenSum >= 0:
    evenOp += abs(evenSum) + 1
    evenSum = -1

print(min(oddOp, evenOp))

Submission status: Accepted

Solution code:
#! /usr/bin/python3

import numpy as np

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

t = 1
ans1 = 0
u = 0

for i in range(n):
    x = s[i] + u
    if t * x <= 0:
        ans1 += abs(x) + 1
        if t == 1:
            u += abs(x) + 1
        else:
            u -= abs(x) + 1
    t *= -1

t = -1
ans2 = 0
u = 0

for i in range(n):
    x = s[i] + u
    if t * x <= 0:
        ans2 += abs(x) + 1
        if t == 1:
            u += abs(x) + 1
        else:
            u -= abs(x) + 1
    t *= -1

print(min(ans1, ans2))