Problem:
 Score : 600 points    Problem Statement Snuke stands on a number line. He has L ears, and he will walk along the line continuously under the following conditions:   He never visits a point with coordinate less than 0 , or a point with coordinate greater than L .  He starts walking at a point with integer coordinate, and also finishes walking at a point with integer coordinate.  He only changes direction at a point with integer coordinate.   Each time when Snuke passes a point with coordinate i-0.5 , where i is an integer, he put a stone in his i -th ear.  After Snuke finishes walking, Ringo will repeat the following operations in some order so that, for each i , Snuke's i -th ear contains A_i stones:   Put a stone in one of Snuke's ears.  Remove a stone from one of Snuke's ears.   Find the minimum number of operations required when Ringo can freely decide how Snuke walks.      Constraints  1 \leq L \leq 2\times 10^5  0 \leq A_i \leq 10^9(1\leq i\leq L)  All values in input are integers.         Input Input is given from Standard Input in the following format:  L  A_1  :  A_L       Output Print the minimum number of operations required when Ringo can freely decide how Snuke walks.        Sample Input 1 4
1
0
2
3      Sample Output 1 1  Assume that Snuke walks as follows:   He starts walking at coordinate 3 and finishes walking at coordinate 4 , visiting coordinates 3,4,3,2,3,4 in this order.   Then, Snuke's four ears will contain 0,0,2,3 stones, respectively.
Ringo can satisfy the requirement by putting one stone in the first ear.       Sample Input 2 8
2
0
0
2
1
3
4
1      Sample Output 2 3       Sample Input 3 7
314159265
358979323
846264338
327950288
419716939
937510582
0      Sample Output 3 1

Solution (Python):
n = int(input())
A = [int(input()) for i in range(n)]

INF = int(1e15)
DP = [[INF] * (n+1) for i in range(5)]
for i in range(4):
    DP[i][0] = 0

for i in range(n):
    DP[0][i+1] = DP[0][i] + A[i]
    DP[1][i+1] = min(DP[j][i] for j in range(2)) + (A[i] % 2 if A[i] != 0 else 2)
    DP[2][i+1] = min(DP[j][i] for j in range(3)) + (A[i] + 1) % 2
    DP[3][i+1] = min(DP[j][i] for j in range(4)) + (A[i] % 2 if A[i] != 0 else 2)
    DP[4][i+1] = min(DP[j][i] for j in range(1, 5)) + A[i]

print(min(DP[i][n] for i in range(1, 5)))

Solution (Python):
n = int(input())
A = [int(input()) for i in range(n)]

INF = int(1e15)
DP = [[INF] * (n+1) for i in range(5)]
for i in range(4):
    DP[i][0] = 0

for i in range(n):
    DP[0][i+1] = DP[0][i] + A[i]
    DP[1][i+1] = min(DP[0][i], DP[1][i]) + (A[i] % 2 if A[i] != 0 else 2)
    DP[2][i+1] = min(DP[0][i], DP[1][i], DP[2][i]) + (A[i] + 1) % 2
    DP[3][i+1] = min(DP[0][i], DP[2][i], DP[3][i]) + (A[i] % 2 if A[i] != 0 else 2)
    DP[4][i+1] = min(DP[2][i], DP[3][i], DP[4][i]) + A[i]

print(min(DP[i][n] for i in range(1, 5)))

Solution (Python):





L = int(input())
A = [int(input()) for i in range(L)]

DP = [[float("inf") for i in range(5)] for j in range(L+1)]
for i in range(5):
    DP[0][i] = 0

def cost(s, i, A):
    if s == 0 or s == 4:
        return A[i]
    elif s == 1 or s == 3:
        if A[i] > 0:
            if A[i]%2 == 0:
                return 0
            else:
                return 1
        else:
            return 2
    else:
        if A[i]%2 == 1:
            return 0
        else:
            return 1

for i in range(L):
    for j in range(5):
        for k in range(j,5):
            DP[i+1][k] = min(DP[i+1][k], DP[i][j]+ cost(k, i, A))



print(min(DP[L]))

Solution (Python):
L = int(input())
a_list = [int(input()) for _ in range(L)]

dp = [[0] * 5 for _ in range(L+1)]

for i in range(L):
    a = a_list[i]

    if a > 0:
        even = a % 2
    else:
        even = 2
    odd = (a + 1) % 2

    
    dp[i+1][0] = dp[i][0] + a
    
    dp[i + 1][1] = min(dp[i][0], dp[i][1]) + even
    
    dp[i + 1][2] = min(dp[i][0], dp[i][1], dp[i][2]) + odd
    
    dp[i + 1][3] = min(dp[i][0], dp[i][1], dp[i][2], dp[i][3]) + even
    
    dp[i + 1][4] = min(dp[i][0], dp[i][1], dp[i][2], dp[i][3], dp[i][4]) + a
print(min(dp[L]))

Solution (Python):
l = int(input())
a = []
for i in range(l):
  a.append(int(input()))
  
dp=[[0]*5 for i in range(l+1)]

for i in range(0,l):
  if a[i]==0:
    even=2
  else:
    even=a[i]%2
  
  dp[i+1][0]=dp[i][0]+a[i]
  dp[i+1][1]=min(dp[i][0],dp[i][1]) + even
  dp[i+1][2]=min(dp[i][0],dp[i][1],dp[i][2]) + (a[i]+1)%2
  dp[i+1][3]=min(dp[i][0],dp[i][1],dp[i][2],dp[i][3]) + even
  dp[i+1][4]=min(dp[i][0],dp[i][1],dp[i][2],dp[i][3],dp[i][4]) + a[i]
  
print(min(dp[l]))

Solution (Python):
L = int(input())
A = [int(input()) for _ in range(L)]
dp = [[0]*5 for _ in range(L)]
dp[0][0] = A[0]
dp[0][1] = A[0] % 2 if A[0] > 0 else 2
dp[0][2] = 1-A[0] % 2
dp[0][3] = A[0] % 2 if A[0] > 0 else 2
dp[0][4] = A[0]
for i in range(1, L):
    dp[i][0] = dp[i-1][0] + A[i]
    tmp = A[i] % 2 if A[i] > 0 else 2
    dp[i][1] = min(dp[i-1][0], dp[i-1][1])+tmp
    tmp = 1-A[i] % 2
    dp[i][2] = min(dp[i-1][0], dp[i-1][1], dp[i-1][2])+tmp
    tmp = A[i] % 2 if A[i] > 0 else 2
    dp[i][3] = min(dp[i-1][0], dp[i-1][1], dp[i-1][2], dp[i-1][3])+tmp
    dp[i][4] = min(dp[i-1][0], dp[i-1][1], dp[i-1]
                   [2], dp[i-1][3], dp[i-1][4]) + A[i]
print(min(dp[L-1]))

Solution (Python):
L = int(input())
A = [int(input()) for _ in range(L)]
dp = [[0]*5 for _ in range(L)]
dp[0][0] = A[0]
dp[0][1] = A[0] % 2 if A[0] > 0 else 2
dp[0][2] = 1-A[0] % 2
dp[0][3] = A[0] % 2 if A[0] > 0 else 2
dp[0][4] = A[0]
for i in range(1, L):
    dp[i][0] = dp[i-1][0] + A[i]
    tmp = A[i] % 2 if A[i] > 0 else 2
    dp[i][1] = min(dp[i-1][0], dp[i-1][1])+tmp
    tmp = 1-A[i] % 2
    dp[i][2] = min(dp[i-1][0], dp[i-1][1], dp[i-1][2])+tmp
    tmp = A[i] % 2 if A[i] > 0 else 2
    dp[i][3] = min(dp[i-1][0], dp[i-1][1], dp[i-1][2], dp[i-1][3])+tmp
    dp[i][4] = min(dp[i-1][0], dp[i-1][1], dp[i-1]
                   [2], dp[i-1][3], dp[i-1][4]) + A[i]
print(min(dp[L-1]))

Solution (Python):
L=int(input())
A=[int(input()) for _ in range(L)]
dp=[[0 for _ in range(5)] for _ in range(L+1)]

for i in range(1,L+1):
    a=A[i-1]
    back = a%2 if a>0 else 2
    through = (a+1)%2


    dp[i][0]=dp[i-1][0]+a
    dp[i][1]=min(dp[i-1][0:2])+back
    dp[i][2]=min(dp[i-1][0:3])+through
    dp[i][3]=min(dp[i-1][0:4])+back
    dp[i][4]=min(dp[i-1][0:5])+a

print(min(dp[L]))

Solution (Python):
L=int(input())
A=[int(input()) for _ in range(L)]
dp=[0 for _ in range(5)]

for a in A:
    back = a%2 if a>0 else 2
    through = (a+1)%2

    dp[4] = min(dp[0:5]) + a
    dp[3] = min(dp[0:4]) + back
    dp[2] = min(dp[0:3]) + through
    dp[1] = min(dp[0:2]) + back
    dp[0] = dp[0]+a

print(min(dp))

Solution (Python):
L=int(input())
A=[int(input()) for _ in range(L)]
dp=[0 for _ in range(5)]

for i in range(1,L+1):
    a=A[i-1]
    back = a%2 if a>0 else 2
    through = (a+1)%2

    dp[4] = min(dp[0:5]) + a
    dp[3] = min(dp[0:4]) + back
    dp[2] = min(dp[0:3]) + through
    dp[1] = min(dp[0:2]) + back
    dp[0]=dp[0]+a

print(min(dp))

Solution (Python):
L=int(input())
A=[int(input()) for _ in range(L)]

INF=2*L

dp=[[INF for _ in range(5)] for _ in range(L+1)]

for j in range(5):
    dp[0][j]=0

for i in range(1,L+1):
    a=A[i-1]

    if A[i-1]==0:
        o=2
    else:
        o=A[i-1]%2

    e=(A[i-1]+1)%2


    dp[i][0]=dp[i-1][0]+a
    dp[i][1]=min(dp[i-1][0]+o,dp[i-1][1]+o)
    dp[i][2]=min(dp[i-1][0]+e,dp[i-1][1]+e,dp[i-1][2]+e)
    dp[i][3]=min(dp[i-1][0]+o,dp[i-1][1]+o,dp[i-1][2]+o,dp[i-1][3]+o)
    dp[i][4]=min(dp[i-1][0]+a,dp[i-1][1]+a,dp[i-1][2]+a,dp[i-1][3]+a,dp[i-1][4]+a)

print(min(dp[L]))

Solution (Python):
L = int(input())
A = [0]*L
for i in range(L):
    A[i] = int(input())
DP = [[float("inf")]*5 for i in range(L+1)]
DP[0][0] = 0

for i in range(L):
    zero = A[i]
    if A[i] == 0:
        even = 2
        odd = 1
    elif A[i]%2==0:
        even = 0
        odd = 1
    else:
        even = 1
        odd = 0
    DP[i+1][0] = DP[i][0] + zero
    DP[i+1][1] = min(DP[i][0], DP[i][1]) + even
    DP[i+1][2] = min(DP[i][0], DP[i][1], DP[i][2]) + odd
    DP[i+1][3] = min(DP[i][0], DP[i][1], DP[i][2], DP[i][3]) + even
    DP[i+1][4] = min(DP[i][0], DP[i][1], DP[i][2], DP[i][3], DP[i][4]) + zero

print(min(DP[L][0], DP[L][1], DP[L][2], DP[L][3], DP[L][4]))

Solution (Python):




def main():
    L = int(input())
    la = []
    for _ in range(L):
        la.append(int(input()))
    dp = [[0 for _ in range(5)] for _ in range(L+1)]

    for i in range(L):
        cost1 = la[i]
        cost2 = 2 if la[i] == 0 else la[i] % 2
        cost3 = 1 if la[i] == 0 else (la[i] + 1) % 2

        dp[i+1][0] = dp[i][0] + cost1
        dp[i+1][1] = min(dp[i][0], dp[i][1]) + cost2
        dp[i+1][2] = min(dp[i][0], dp[i][1], dp[i][2]) + cost3
        dp[i+1][3] = min(dp[i][0], dp[i][1], dp[i][2], dp[i][3]) + cost2
        dp[i+1][4] = min(dp[i][0], dp[i][1], dp[i][2], dp[i][3], dp[i][4]) + cost1

    print(min(dp[L]))


if __name__ == '__main__':
    main()

Solution (Python):
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**8) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())


def to0or4(base: int, nex: int):
    return base + nex


def to1or3(base: int, nex: int):
    if nex == 0:
        return base + 2
    
    elif nex % 2:
        return base + 1
    
    else:
        return base



def to2(base: int, nex: int):
    if nex % 2:
        return base
    
    else:
        return base + 1
    
n = ni()
a = [ni() for _ in range(n)]
suma = sum(a)  


dp = [[suma]*5 for _ in range(n+1)]
dp[0] = [0]*5

for i in range(n):
    for idx in range(5):
        for jdx in range(idx,5):
            
            if jdx == 0 or jdx == 4:
                dp[i+1][jdx] = min(dp[i+1][jdx],
                                   to0or4(dp[i][idx], a[i]))
            
            elif jdx == 1 or jdx == 3:
                dp[i+1][jdx] = min(dp[i+1][jdx],
                                   to1or3(dp[i][idx], a[i]))
                
            elif jdx == 2:
                dp[i+1][jdx] = min(dp[i+1][jdx],
                                   to2(dp[i][idx], a[i]))
   
print(min(dp[n]))

Solution (Python):


L = int(input())
A = [int(input()) for _ in  range(L)]


DP = [0] * 5
for i in range(L):
    r0 = A[i]
    r1 = (A[i] + 1) % 2

    if A[i] == 0:
        r2 = 2
    else:
        r2 = A[i] % 2

    for i,r in zip(range(4,-1,-1), [r0,r2,r1,r2,r0]):
        DP[i] = min(DP[:i+1]) + r
        

print(min(DP))

Solution (Python):
def cost(place,zone):
    if zone == 0 or zone == 4:
        return A[place]
    elif zone == 1 or zone == 3:
        if A[place] == 0:
            return 2
        elif A[place] % 2 == 0:
            return 0
        else:
            return 1
    else:
        if A[place] % 2 == 0:
            return 1
        else:
            return 0

if __name__=='__main__':
    L = int(input())
    A = [int(input()) for i in range(L)]

    
    dp = [[0 for _ in range(5)] for _ in range(L+10)]
    
    for j in range(5):
        dp[0][j] = cost(0,j)
    
    for i in range(1,L):
        dp[i][0] = dp[i-1][0]+cost(i,0)
        for j in range(1,5):
            
            dp[i][j] = min(min(dp[i-1][0:j+1])+cost(i,j),dp[i][j-1])
    
    print(min(dp[L-1]))

Solution (Python):
L = int(input())
A = [int(input()) for i in range(L)]

dp = [[0 for _ in range(5)] for _ in range(L)]



def cost(place,zone):
    if zone == 0 or zone == 4:
        return A[place]
    elif zone == 1 or zone == 3:
        if A[place] == 0:
            return 2
        elif A[place] % 2 == 0:
            return 0
        else:
            return 1
    else:
        if A[place] % 2 == 0:
            return 1
        else:
            return 0

for j in range(5):
    dp[0][j] = cost(0,j)


for i in range(L):
    for j in range(5):
        dp[i][j] = min(dp[i-1][0:j+1])+cost(i,j)
print(min(dp[L-1]))

Solution (Python):
L = int(input())
A_list = [0]*L
for i in range(L):
    A_list[i] = int(input())

DP = [0]*5
for i in range(L):
    
    r0 = A_list[i]
    
    r1 = (A_list[i] + 1) % 2
    
    if A_list[i] == 0:
        r2 = 2
    else:
        r2 = A_list[i] % 2
    
    DP[4] = min(DP[0], DP[1], DP[2], DP[3], DP[4]) + r0
    DP[3] = min(DP[0], DP[1], DP[2], DP[3]) + r2
    DP[2] = min(DP[0], DP[1], DP[2]) + r1
    DP[1] = min(DP[0], DP[1]) + r2
    DP[0] = DP[0] + r0
    
print(min(DP))

Solution (Python):
a = [int(input()) for _ in range(int(input()))]

dp = [[0] * 5 for _ in range(len(a) + 1)]

for i, x in enumerate(a):
    m = x % 2
    y = m + (not x) * 2
    z = 1 - m
    
    dp[i+1][0] = dp[i][0] + x
    dp[i+1][1] = min(dp[i][:2]) + y
    dp[i+1][2] = min(dp[i][:3]) + z
    dp[i+1][3] = min(dp[i][:4]) + y
    dp[i+1][4] = min(dp[i]) + x

print(min(dp[-1]))

Solution (Python):
a = [int(input()) for _ in range(int(input()))]

dp = [[0] * 5 for _ in range(len(a) + 1)]

for i, x in enumerate(a):
    m = x % 2
    y = m + (x == 0) * 2
    z = 1 - m
    
    dp[i+1][0] = dp[i][0] + x
    dp[i+1][1] = min(dp[i][:2]) + y
    dp[i+1][2] = min(dp[i][:3]) + z
    dp[i+1][3] = min(dp[i][:4]) + y
    dp[i+1][4] = min(dp[i]) + x

print(min(dp[-1]))

Solution (Python):
a = [int(input()) for _ in range(int(input()))]

dp = [[0] * 5 for _ in range(len(a) + 1)]

for i, x in enumerate(a):
    y = x % 2 + (x == 0) * 2
    z = (x + 1) % 2
    
    dp[i+1][0] = dp[i][0] + x
    dp[i+1][1] = min(dp[i][:2]) + y
    dp[i+1][2] = min(dp[i][:3]) + z
    dp[i+1][3] = min(dp[i][:4]) + y
    dp[i+1][4] = min(dp[i]) + x

print(min(dp[-1]))

Solution (Python):
a = [int(input()) for _ in range(int(input()))]

dp = [[0] * 5 for _ in range(len(a) + 1)]

for i, x in enumerate(a):
    y = x % 2 + (x == 0) * 2
    z = (x + 1) % 2
    
    dp[i+1][0] = min(dp[i][0:1]) + x
    dp[i+1][1] = min(dp[i][0:2]) + y
    dp[i+1][2] = min(dp[i][0:3]) + z
    dp[i+1][3] = min(dp[i][0:4]) + y
    dp[i+1][4] = min(dp[i][0:5]) + x

print(min(dp[-1]))

Solution (Python):


L = int(input())
A = [int(input()) for _ in range(L)]

DP = [0] * 5



for i in range(L):
    DP[4] = min(DP[0:5]) + A[i]
    DP[3] = min(DP[0:4]) + (A[i] % 2 if A[i] != 0 else 2)
    DP[2] = min(DP[0:3]) + ((A[i] + 1) % 2)
    DP[1] = min(DP[0:2]) + (A[i] % 2 if A[i] != 0 else 2)
    DP[0] = DP[0] + A[i]

print(min(DP))

Solution (Python):
l = int(input())
a = [int(input()) for _ in range(l)]

ans = [[0] * 5 for _ in range(l + 1)]
for n in range(1, l + 1):
    c = a[n - 1]
    ans[n][0] = ans[n - 1][0] + c
    ans[n][1] = min(ans[n - 1][:2]) + (c % 2 if c > 0 else 2)
    ans[n][2] = min(ans[n - 1][:3]) + (c + 1) % 2
    ans[n][3] = min(ans[n - 1][:4]) + (c % 2 if c > 0 else 2)
    ans[n][4] = min(ans[n - 1][:5]) + c

print(min(ans[l]))

Solution (Python):



def zr(x):
    return x


def ev(x):
    return x % 2 if x > 0 else 2


def od(x):
    return (x + 1) % 2 if x > 0 else 1


INF = 10**9 + 1

L = int(input())
A = [int(input()) for _ in range(L)]

dp = [[0] * 5] + [[INF] * 5 for _ in range(L)]
for i, x in enumerate(A):
    for t, f in enumerate([zr, ev, od, ev, zr]):
        dp[i + 1][t] = min(dp[i + 1][t], min(dp[i][:t + 1]) + f(x))

print(min(dp[L]))

Solution (Python):



def f(x):
    return x % 2 if x > 0 else 2


def g(x):
    return (x - 1) % 2 if x > 0 else 1


INF = 10**9 + 1

L = int(input())
A = [int(input()) for _ in range(L)]

dp = [[0] * 5] + [[INF] * 5 for _ in range(L)]
for i in range(L):
    dp[i + 1][0] = min(dp[i + 1][0], min(dp[i][:1]) + A[i])
    dp[i + 1][1] = min(dp[i + 1][1], min(dp[i][:2]) + f(A[i]))
    dp[i + 1][2] = min(dp[i + 1][2], min(dp[i][:3]) + g(A[i]))
    dp[i + 1][3] = min(dp[i + 1][3], min(dp[i][:4]) + f(A[i]))
    dp[i + 1][4] = min(dp[i + 1][4], min(dp[i][:5]) + A[i])

print(min(dp[L]))

Solution (Python):
n = int(input())
arr = [int(input()) for _ in range(n)]
def ear(n,t):
    if n:
        if t == 1 or t == 3:
            return n%2
        elif t == 2:
            return (n-1)%2
        else:
            return n
    else:
        if t == 1 or t == 3:
            return 2
        elif t == 2:
            return 1
        else:
            return 0
dp = [[0]*5 for _ in range(n)]
for i in range(n):
    for t in range(5):
        if i == 0:
            dp[i][t] = ear(arr[i],t)
        else:
            if t == 0:
                mind = dp[i-1][t]
                dp[i][t] = ear(arr[i],t) + mind
            else:
                if mind > dp[i-1][t]:
                    mind = dp[i-1][t]
                dp[i][t] = ear(arr[i],t) + mind
            dp[i][t] = ear(arr[i],t) + mind
print(min(dp[n-1]))

Solution (Python):
L = int(input())

inf = float('inf')
dp = [[inf] * 5 for _ in range(L+1)]
dp[0][0] = 0
for i in range(1, L+1):
    a = int(input())

    b = a & 1
    c = b ^ 1
    p, n = dp[i-1], dp[i]
    n[0] = p[0] + a
    n[1] = min(p[:2]) + b
    n[2] = min(p[:3]) + c
    n[3] = min(p[:4]) + b
    n[4] = min(p[:5]) + a

    if a == 0:
        n[1] += 2
        n[3] += 2

print(min(dp[L]))

Solution (Python):
l=int(input())
A=[int(input()) for _ in range(l)]

def even(n):
    if n==0:
        return 2
    else:
        return n%2
def odd(n):
    return (n+1)%2

DP=[[0]*5 for _ in range(l)]
DP[0]=[A[0],even(A[0]),odd(A[0]),even(A[0]),A[0]]
for i in range(1,l):
    DP[i][0]=DP[i-1][0]+A[i]
    DP[i][1]=min(DP[i-1][:2])+even(A[i])
    DP[i][2]=min(DP[i-1][:3])+odd(A[i])
    DP[i][3]=min(DP[i-1][:4])+even(A[i])
    DP[i][4]=min(DP[i-1])+A[i]
print(min(DP[l-1]))

Solution (Python):
l = int(input())
a = [int(input()) for _ in range(l)]

INF = float('inf')
dp = [[INF] * 5 for _ in range(l+10)]
dp[0][0] = 0

for i in range(l):
    for j in range(4):
        dp[i][j+1] = min(dp[i][j+1], dp[i][j])

    dp[i + 1][0] = min(dp[i + 1][0], dp[i][0] + a[i])
    dp[i + 1][1] = min(dp[i + 1][1], dp[i][1] + a[i] % 2 if a[i] > 0 else dp[i][1] + 2)
    dp[i + 1][2] = min(dp[i + 1][2], dp[i][2] + (a[i] + 1) % 2)
    dp[i + 1][3] = min(dp[i + 1][3], dp[i][3] + a[i] % 2 if a[i] > 0 else dp[i][3] + 2)
    dp[i + 1][4] = min(dp[i + 1][4], dp[i][4] + a[i])

ans = float('inf')
for j in range(5):
    ans = min(ans, dp[l][j])

print(ans)

Solution (Python):
l = int(input())
a = [int(input()) for _ in range(l)]

dp = [[0]*5 for _ in range(l)]

if a[0] == 0:
    dp[0] = [a[0],2,1,2,a[0]]
elif a[0]%2 == 0:
    dp[0] = [a[0],0,1,0,a[0]]
else:
    dp[0] = [a[0],1,0,1,a[0]]

for i in range(1,l):
    dp[i][0] = dp[i-1][0]+a[i]
    dp[i][2] = min(dp[i-1][0:3])+1-a[i]%2
    dp[i][4] = min(dp[i-1][0:5])+a[i]
    if a[i]!=0:
        dp[i][3] = min(dp[i-1][0:4])+a[i]%2
        dp[i][1] = min(dp[i-1][0], dp[i-1][1])+a[i]%2
    else:
        dp[i][3] = min(dp[i-1][0:4])+2
        dp[i][1] = min(dp[i-1][0], dp[i-1][1])+2

print(min(dp[l-1]))

Solution (Python):
l=int(input())
a=[int(input()) for x in range(l)]
def ds_tu(i):
    if a[i]==0:return 2
    return a[i]%2
ans=[[0 for i in range(5)] for j in range(l)]
ans[0][0]=a[0]
ans[0][1]=ds_tu(0)
ans[0][2]=(a[0]+1)%2
ans[0][3]=ds_tu(0)
ans[0][4]=a[0]
for i in range(1,l):
    ans[i][0]=ans[i-1][0]+a[i]
    ans[i][1]=min(ans[i-1][0:2])+ds_tu(i)
    ans[i][2]=min(ans[i-1][0:3])+(a[i]+1)%2
    ans[i][3]=min(ans[i-1][0:4])+ds_tu(i)
    ans[i][4]=min(ans[i-1])+a[i]
    
print(min(ans[l-1]))

Solution (Python):
L = int(input())
A = [0] * (L + 1)
DP = [[0, 0, 0, 0, 0] for i in range(L + 1)]
for i in range(L):
  a = int(input())
  DP[i + 1][0] = DP[i][0] + a
  DP[i + 1][1] = min(min(DP[i][:2]), DP[i + 1][0]) + (a % 2 if a else 2)
  DP[i + 1][2] = min(min(DP[i][:3]), DP[i + 1][1]) + ((1 - a % 2) if a else 1)
  DP[i + 1][3] = min(min(DP[i][:4]), DP[i + 1][2]) + (a % 2 if a else 2)
  DP[i + 1][4] = min(min(DP[i]), DP[i + 1][3]) + a
print(min(DP[L]))

Solution (Python):
MOD = 998244353
n = int(input())
a = [int(input()) for _ in range(n)] + [0]
dp = [[float("inf") for _ in range(5)] for _ in range(n+1)]
def ev(x):
	if x == 0:
		return 2
	else:
		return x&1
def od(x):
	return (x+1)&1

dp[0] = [a[0], ev(a[0]), od(a[0]), ev(a[0]), a[0]]
for i in range(1, n+1):
	dp[i][0] = dp[i-1][0] + a[i]
	dp[i][1] = min(dp[i-1][:2]) + ev(a[i])
	dp[i][2] = min(dp[i-1][:3]) + od(a[i])
	dp[i][3] = min(dp[i-1][:4]) + ev(a[i])
	dp[i][4] = min(dp[i-1]) + a[i]
print(min(dp[n]))

Solution (Python):

L = int(input())
A_list = [0]*L
for i in range(L):
    A_list[i] = int(input())
    
DP = [0]*5
for i in range(L):
    r0 = A_list[i]
    r1 = (A_list[i] + 1) % 2
    if A_list[i] == 0:
        r2 = 2
    else:
        r2 = A_list[i] % 2
        
    DP[4] = min(DP[0], DP[1], DP[2], DP[3], DP[4]) + r0
    DP[3] = min(DP[0], DP[1], DP[2], DP[3]) + r2
    DP[2] = min(DP[0], DP[1], DP[2]) + r1
    DP[1] = min(DP[0], DP[1]) + r2
    DP[0] = DP[0] + r0
    
print(min(DP))

Solution (Python):
L = int(input())
a=[int(input()) for i in range(L)]
if L == 1:
    print(0)
    exit()


rightsum = [0]*(L+1)
leftsum = [0]*(L+1)
for i in range(1,L+1):
    rightsum[i] = rightsum[i-1]+a[i-1]
    leftsum[i] = leftsum[i-1]+a[L-i]


Reright = [0]
Goright = [0]
for i in range(L):
    if a[i] == 0:
        Goright.append(min(rightsum[i+1],1+min(Goright[-1],Reright[-1])))
        Reright.append(min(rightsum[i+1],2+Reright[-1]))
    else:
        Goright.append(min(rightsum[i+1],(a[i]+1)%2+min(Goright[-1],Reright[-1])))
        Reright.append(min(rightsum[i+1],a[i]%2+Reright[-1]))
        
Releft = [0]
Goleft = [0]
for i in range(L):
    if a[L-1-i]==0:
        Releft.append(min(leftsum[i+1],2+Releft[-1]))
        Goleft.append(min(leftsum[i+1],1+min(Goleft[-1],Releft[-1])))
    else:
        Goleft.append(min(leftsum[i+1],(a[L-1-i]+1)%2+min(Goleft[-1],Releft[-1])))
        Releft.append(min(leftsum[i+1],a[L-1-i]%2+Releft[-1]))
        

cand = []
for i in range(L+1):
    p1 = Reright[i]
    p2 = min(Reright[i],Goright[i])
    q1 = Releft[L-i]
    q2 = min(Releft[L-i],Goleft[L-i])
    cand.append(min(p1+q2,p2+q1))
    
print(min(cand))

Solution (Python):
L = int(input())
A = [int(input()) for i in range(L)]

Asum = [0]
for i, a in enumerate(A):
    Asum.append(Asum[i] + a)

Emin = [0 for i in range(L + 1)]
Zmin = [0 for i in range(L + 1)]

for i in range(L)[:: -1]:
    a = A[i]
    if a == 0:
        Emin[i] = 2 + Emin[i + 1]
        Zmin[i] = 1 + min(Emin[i + 1], Zmin[i + 1])
    elif a % 2 == 0:
        Emin[i] = Emin[i + 1]
        Zmin[i] = 1 + min(Emin[i + 1], Zmin[i + 1])
    else:
        Emin[i] = 1 + Emin[i + 1]
        Zmin[i] = min(Emin[i + 1], Zmin[i + 1])
    Emin[i] = min(Emin[i], Asum[L] - Asum[i])
    Zmin[i] = min(Zmin[i], Asum[L] - Asum[i])


A.reverse()

Asum = [0]
for i, a in enumerate(A):
    Asum.append(Asum[i] + a)

Emin2 = [0 for i in range(L + 1)]
Zmin2 = [0 for i in range(L + 1)]

for i in range(L)[:: -1]:
    a = A[i]
    if a == 0:
        Emin2[i] = 2 + Emin2[i + 1]
        Zmin2[i] = 1 + min(Emin2[i + 1], Zmin2[i + 1])
    elif a % 2 == 0:
        Emin2[i] = Emin2[i + 1]
        Zmin2[i] = 1 + min(Emin2[i + 1], Zmin2[i + 1])
    else:
        Emin2[i] = 1 + Emin2[i + 1]
        Zmin2[i] = min(Emin2[i + 1], Zmin2[i + 1])
    Emin2[i] = min(Emin2[i], Asum[L] - Asum[i])
    Zmin2[i] = min(Zmin2[i], Asum[L] - Asum[i])

ans = 3000000
for i in range(L):
    ans = min(ans, min(Emin[i], Zmin[i]) + min(Emin2[L - i], Zmin2[L - i]))

print(ans)

Solution (Python):

def main():
    buf = input()
    L = int(buf)
    A = []
    for i in range(L):
        buf = input()
        A.append(int(buf))
    print(min(calc_move_count(A), calc_move_count(list(reversed(A)))))

def calc_move_count(A):
    stone_diff = []
    for i in A:
        if i == 0:
            stone_diff.append(1)
        elif i % 2 == 0:
            stone_diff.append(-1)
        else:
            stone_diff.append(0)
    no_left_sum = []
    for i in reversed(stone_diff):
        if not no_left_sum:
            no_left_sum.append(abs(i))
        else:
            no_left_sum.append(no_left_sum[-1] + abs(i))
    no_left_sum = list(reversed(no_left_sum))
    no_left_sum.append(0)
    move_left = [0]
    for i in A:
        if not move_left:
            move_left.append(i)
        else:
            move_left.append(move_left[-1] + i)
    move_right = []
    for i in reversed(A):
        if not move_right:
            move_right.append(i)
        else:
            move_right.append(move_right[-1] + i)
    move_right = list(reversed(move_right))
    move_right.append(0)
    dp = [[0, no_left_sum[0], 0, move_right[0]]]
    for i in range(len(A)):
        l = []
        l.append(min(move_left[i+1], dp[-1][0]+abs(stone_diff[i]+1)))
        l.append(min(move_left[i+1], l[0], dp[-1][1]+abs(stone_diff[i])-no_left_sum[i]) + no_left_sum[i+1])
        l.append(min(move_left[i+1], l[1]-no_left_sum[i+1], dp[-1][2]+abs(stone_diff[i]+1)))
        l.append(min(dp[-1][3], l[2] + move_right[i+1]))
        dp.append(l)
    return dp[-1][3]


if __name__ == '__main__':
    main()

Solution (Python):
L = int(input())
a=[int(input()) for i in range(L)]
if L == 1:
    print(0)
    exit()
    
rightsum = [0]*(L+1)
leftsum = [0]*(L+1)
for i in range(1,L+1):
    rightsum[i] = rightsum[i-1]+a[i-1]
    leftsum[L-i] = leftsum[L+1-i]+a[L-i]
leftsum=leftsum[::-1]

Reright = [0]
Goright = [0]
for i in range(L):
    res = Reright[-1] 
    if a[i] == 0:
        Reright.append(min(rightsum[i+1],2+Reright[-1]))
        Goright.append(min(rightsum[i+1],1+min(Goright[-1],res)))
    else:
        Reright.append(min(rightsum[i+1],a[i]%2+Reright[-1]))
        Goright.append(min(rightsum[i+1],(a[i]+1)%2+min(Goright[-1],res)))
Releft = [0]
Goleft = [0]

for i in range(L):
    res = Releft[-1]
    if a[L-1-i]==0:
        Releft.append(min(leftsum[i+1],2+Releft[-1]))
        Goleft.append(min(leftsum[i+1],1+min(Goleft[-1],res)))
    else:
        Releft.append(min(leftsum[i+1],a[L-1-i]%2+Releft[-1]))
        Goleft.append(min(leftsum[i+1],(a[L-1-i]+1)%2+min(Goleft[-1],res)))



cand = []
for i in range(L+1):
    p1 = Reright[i]
    p2 = min(Reright[i],Goright[i])
    q1 = Releft[L-i]
    q2 = min(Releft[L-i],Goleft[L-i])
    cand.append(min(p1+q2,p2+q1))
    
print(min(cand))

Solution (Python):
L = int(input())
A = [int(input()) for _ in range(L)]

INF = 1E50
ans1 = sum(A)  
ans2 = ans1 - 1 if ans1 > 0 else 0

a_alpha_t = list(map(lambda x: 2 if x == 0 else x % 2, A))
a_b_t = list(map(lambda x: (x + 1) % 2, A))

total_val = 0
a_b_val = 0
a_alpha_val = 0
total = [0 for _ in range(L)]
a_b = list(total)
a_alpha = list(total)
for i in range(L):
    total_val += A[i]
    a_b_val += a_b_t[i]
    a_alpha_val += a_alpha_t[i]
    total[i] = total_val
    a_b[i] = a_b_val
    a_alpha[i] = a_alpha_val








ans = [0 for _ in range(5)]
for i, a in enumerate(A):
    tmp_ans=  [INF for _ in range(5)]
    tmp_ans[0] = total[i]
    tmp_ans[1] = min(ans[1]+a_alpha_t[i],total[i])
    tmp_ans[2]= min(tmp_ans[1],ans[2]+a_b_t[i])
    tmp_ans[3]= min(tmp_ans[2],ans[3]+a_alpha_t[i])
    tmp_ans[4] = min(tmp_ans[3],ans[4]+A[i])
    ans = tmp_ans

print(min(ans+[ans1,ans2]))

Solution (Python):


"""

o 999
o 2 3
x 2 0 2
o 2 1 2
x 2 1 2 1
o 2 1 3 1
o 2 1 3 2
o 3 1 3
x 3 2 3
o 3 2 2

- 0は両端のみ
- 偶奇の切り替わりが2回以下

0 zzoo
1 zzee
2 zzooee
3 zzeeoo
4 zzeeooee
5 zz
6 ???zz
"""

L = input()
A = [input() for _ in range(L)]

T = [L,L,L,L,L,0,L]
for a in A:
  P = T
  o = 1-a%2
  e = 1-o
  if a==0:
    e = 2
  T = [
    min(P[0]+o, P[5]+o),
    min(P[1]+e, P[5]+e),
    min(P[2]+e, P[0]+e),
    min(P[3]+o, P[1]+o),
    min(P[4]+e, P[3]+e),
    P[5]+a,
    min(P)+a,
  ]
  
print min(T)

Solution (Python):
l = int(input())
aList = [int(input()) for _ in range(l)]

INF = 10 ** 6

dp = [[INF] * (l + 1) for _ in range(5)]
for i in range(5):
    dp[i][0] = 0
for i in range(l):
    for state in range(5):
        if state == 4:
            dp[state][i + 1] = min(dp[j][i] for j in range(state + 1)) + aList[i]
        elif state == 3:
            dp[state][i + 1] = min(dp[j][i] for j in range(state + 1)) + (aList[i] % 2 if aList[i] != 0 else 2)
        elif state == 2:
            dp[state][i + 1] = min(dp[j][i] for j in range(state + 1)) + (aList[i] - 1) % 2

        elif state == 1:
            dp[state][i + 1] = min(dp[j][i] for j in range(state + 1)) + (aList[i] % 2 if aList[i] != 0 else 2)
        else:
            dp[state][i + 1] = min(dp[j][i] for j in range(state + 1)) + aList[i]
            
ans = INF
for i in range(5):
    ans = min(ans, dp[i][l])
print(ans)

Solution (Python):




l = int(input())
a = [int(input()) for i in [0]*l]
asum=[0]*(l+1)
for i in range(1,l+1):
    asum[i] = asum[i-1]+a[i-1]    

reven=[0]*(l+1)
leven=[0]*(l+1)
rodd=[0]*(l+1)
lodd=[0]*(l+1)

for i in range(1,l+1):
    if a[i-1] != 0:
        leven[i]=leven[i-1] + a[i-1]%2
    else:
        leven[i]=min(2+leven[i-1],asum[i])

for i in range(l-1,-1,-1):
    if a[i] != 0:
        reven[i]=reven[i+1] + a[i]%2
    else:
        reven[i]=min(2+reven[i+1],asum[l]-asum[i])

for i in range(1,l+1):
    lodd[i]=min(leven[i], lodd[i-1]+(a[i-1]+1)%2, asum[i])

for i in range(l-1,-1,-1):
    rodd[i]=min(reven[i], rodd[i+1]+(a[i]+1)%2, asum[l]-asum[i])







ans = 5*(l+2)
for i in range(l+1):
    ans = min(ans, leven[i]+rodd[i], lodd[i]+reven[i])

print(ans)

Solution (Python):
L = int(input())
A = [int(input()) for i in range(L)]
dp = [[0]*5 for _ in range(L+1)]
for i in range(1, L+1):
    a = A[i-1]
    g = a%2
    dp[i][0] = dp[i-1][0] + a
    dp[i][1] = min(dp[i-1][:2]) + (g if a!=0 else 2)
    dp[i][2] = min(dp[i-1][:3]) + (1-g if a!=0 else 1)
    dp[i][3] = min(dp[i-1][:4]) + (g if a!=0 else 2)
    dp[i][4] = min(dp[i-1]) + a
print(min(dp[-1]))

Solution (Python):
L, = map(int, raw_input().split())
A = [0]*L
dp = []
for i in xrange(L):
  A[i], = map(int, raw_input().split())
  dp.append([float("inf")]*5)
i=0
e = 2-A[i] if A[i]<2 else A[i]%2
o = 1 if A[i]==0 else (A[i]+1)%2
dp[0][0] = A[0]
dp[0][1] = e
dp[0][2] = o
dp[0][3] = e
dp[0][4] = A[0]
for i in xrange(1, L):
  e = 2-A[i] if A[i]<2 else A[i]%2
  o = 1 if A[i]==0 else (A[i]+1)%2
  dp[i][0] = min(dp[i-1][:1]) + A[i]
  dp[i][1] = min(dp[i-1][:2]) + e
  dp[i][2] = min(dp[i-1][:3]) + o
  dp[i][3] = min(dp[i-1][:4]) + e
  dp[i][4] = min(dp[i-1][:5]) + A[i]
print min(dp[-1])

Solution (Python):
from sys import stdin
from itertools import repeat
def main():
    n = int(stdin.readline())
    a = [int(stdin.readline()) for _ in xrange(n)]
    while a and not a[-1]:
        a.pop()
    a.reverse()
    while a and not a[-1]:
        a.pop()
    n = len(a)
    p = [0] * n
    q = [0] * n
    for i in xrange(n):
        if not a[i]:
            p[i] = 1
            q[i] = 2
        else:
            p[i] = 1 - a[i] % 2
            q[i] = a[i] % 2
    l = [(0, 0, 0)] * (n + 1)
    r = [(0, 0, 0)] * (n + 1)
    for i in xrange(n):
        l[i+1] = (l[i][0] + a[i], min(l[i][0], l[i][1]) + q[i], min(l[i]) + p[i])
    for i in xrange(n - 1, -1, -1):
        r[i] = (r[i+1][0] + a[i], min(r[i+1][0], r[i+1][1]) + q[i], min(r[i+1]) + p[i])
    ans = min(min(l[i]) + min(r[i]) for i in xrange(n + 1))
    print ans
main()

Solution (Python):
L = int(input())
A = [int(input()) for i in range(L)]
X = [[0] * 5 for _ in range(L+1)]

X[0] = [0] * 5
for i in range(L):
    X[i+1][0] = X[i][0] + A[i]
    X[i+1][1] = min(X[i][0], X[i][1]) + (A[i] % 2 if A[i] > 0 else 2)
    X[i+1][2] = min(X[i][0], X[i][1], X[i][2]) + ((A[i]+1) % 2)
    X[i+1][3] = min(X[i][0], X[i][1], X[i][2], X[i][3]) + (A[i] % 2 if A[i] > 0 else 2)
    X[i+1][4] = min(X[i][0], X[i][1], X[i][2], X[i][3], X[i][4]) + A[i]

print(min(X[-1]))