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):
import sys
input = sys.stdin.readline

L=int(input())
A=[int(input()) for i in range(L)]
            
SUM=[0]
for a in A:
    SUM.append(SUM[-1]+a)

def div2(x):
    if x==0:
        return 2
    else:
        return x%2
    
DP0=[0]*(L+1)
DP1=[0]*(L+1)
DP2=[0]*(L+1)
DP3=[0]*(L+1)
DP4=[0]*(L+1)

for i in range(L):
    DP0[i]=DP0[i-1]+A[i]
    DP1[i]=min(DP0[i-1]+div2(A[i]),DP1[i-1]+div2(A[i]))
    DP2[i]=min(DP2[i-1]+(A[i]+1)%2,DP1[i-1]+(A[i]+1)%2,DP0[i-1]+(A[i]+1)%2)
    DP3[i]=min(DP3[i-1]+div2(A[i]),DP2[i-1]+div2(A[i]),DP1[i-1]+div2(A[i]),DP0[i-1]+div2(A[i]))
    DP4[i]=min(DP4[i-1]+A[i],DP3[i-1]+A[i],DP2[i-1]+A[i],DP1[i-1]+A[i],DP0[i-1]+A[i])

print(min(DP0[L-1],DP1[L-1],DP2[L-1],DP3[L-1],DP4[L-1]))

Solution (Python):

import sys

INF = float('inf')

def solve(n: int, A: "List[int]"):
    dp = [[INF] * 5  for _ in range(n + 1)]
    dp[0][0] = 0
    dp[0][1] = 0
    dp[0][2] = 0
    for i in range(n):
        for j in range(5):
            if j == 0 or j == 4:
                extra = A[i]
            elif j == 1 or j == 3:
                extra = A[i] % 2 if A[i] > 0 else 2
            else:
                extra = (A[i] + 1) % 2
            dp[i + 1][j] = min(dp[i + 1][j], dp[i][j] + extra)
            for k in range(j + 1, 5):
                dp[i + 1][k] = min(dp[i + 1][k], dp[i][j] + extra)
        
    print(min(dp[n]))
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    L = int(next(tokens))  
    A = [ int(next(tokens)) for _ in range(L) ]  
    solve(L, A)

if __name__ == '__main__':
    main()

Solution (Python):

import sys

INF = float('inf')

def solve(n: int, A: "List[int]"):
    dp = [[INF] * 5  for _ in range(n + 1)]
    dp[0][0] = 0
    dp[0][1] = 0
    dp[0][2] = 0
    for i in range(n):
        for j in range(5):
            if j == 0 or j == 4:
                extra = A[i]
            elif j == 1 or j == 3:
                extra = A[i] % 2 if A[i] > 0 else 2
            else:
                extra = (A[i] + 1) % 2
            dp[i + 1][j] = min(dp[i][:j + 1]) + extra
        
    print(min(dp[n]))
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    L = int(next(tokens))  
    A = [ int(next(tokens)) for _ in range(L) ]  
    solve(L, A)

if __name__ == '__main__':
    main()

Solution (Python):
import sys
sys.setrecursionlimit(200000)
input = sys.stdin.readline
n = int(input())
a = [int(input()) for i in range(n)]
dp = [[1<<60]*5 for i in range(n+1)]
dp[0][0] = 0
for i in range(n):
        dp[i+1][0] = dp[i][0]+a[i]
        if a[i] != 0:
                dp[i+1][1] = min(dp[i][0]+a[i]%2,dp[i][1]+a[i]%2)
        else:
                dp[i+1][1] = min(dp[i][0]+2,dp[i][1]+2)
        a[i]+=1
        dp[i+1][2] = min(dp[i][0]+a[i]%2,dp[i][1]+a[i]%2,dp[i][2]+a[i]%2)
        a[i]-=1
        if a[i] != 0:
                dp[i+1][3] = min(dp[i][0]+a[i]%2,dp[i][1]+a[i]%2,dp[i][2]+a[i]%2,dp[i][3]+a[i]%2)
        else:
                dp[i+1][3] = min(dp[i][0]+2,dp[i][1]+2,dp[i][2]+2,dp[i][3]+2)
        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[n]))

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

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

def cost(s, a):
    if s == 0 or s == 4:
        return a
    elif s == 1 or s == 3:
        if a > 0:
            return a%2
        else:
            return 2
    else:
        return (a+1)%2

for i in range(L):
    DP[i+1][0] = min(DP[i][:1]) + cost(0, A[i])
    DP[i+1][1] = min(DP[i][:2]) + cost(1, A[i])
    DP[i+1][2] = min(DP[i][:3]) + cost(2, A[i])
    DP[i+1][3] = min(DP[i][:4]) + cost(3, A[i])
    DP[i+1][4] = min(DP[i][:5]) + cost(4, A[i])

print(min(DP[L]))

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


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

mod=A[0]%2
if A[0]==0 :
    mod=2
DP[1]=[A[0],min(A[0],mod%2),min(A[0],mod%2,(mod+1)%2),min(A[0],mod%2,(mod+1)%2),min(A[0],mod%2,(mod+1)%2)]

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


print(min(DP[L]))

Solution (Python):
L=int(input())
dp=[0]*5
for i in range(L):
  A=int(input())
  
  even=A%2
  if A==0:
    even=2
  odd=(A+1)%2
  
  
  dp[4]=min(dp[:])+A
  dp[3]=min(dp[:4])+even
  dp[2]=min(dp[:3])+odd
  dp[1]=min(dp[:2])+even
  dp[0]=dp[0]+A
  
print(min(dp))

Solution (Python):
L, *A = map(int, open(0).read().split())
a0 = a1 = a2 = a3 = a4 = 0
rest = sum(A)
P = [2, 1, 0]
Q = [1, 0, 1]
for a in A:
    b = (a - 1) % 2 + 1 if a else 0
    p = P[b]; q = Q[b]
    a0 += a
    a1 = min(a0, a1 + p)
    a2 = min(a1, a2 + q)
    a3 = min(a2, a3 + p)
    a4 = min(a3, a4 + a)
print(min(a0, a1, a2, a3, a4))

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

b = []

for i in range(a):
	b.append(int(input()))

c = [[0] * 5 for i in range(a+1)]

for i in range(a):
	c[i+1][0] = c[i][0] + b[i]
	c[i+1][1] = min(c[i][0],c[i][1]) + (b[i] % 2 if b[i] > 0 else 2)
	c[i+1][2] = min(c[i][0],c[i][1],c[i][2]) + ((b[i]+1) % 2)
	c[i+1][3] = min(c[i][0],c[i][1],c[i][2],c[i][3]) + (b[i] % 2 if b[i] > 0 else 2)
	c[i+1][4] = min(c[i][0],c[i][1],c[i][2],c[i][3],c[i][4]) + b[i]

print(min(c[-1]))

Solution (Python):
def main():
    l = int(input())
    nums = [int(input()) for _ in range(l)]
    dp = [[0 for _ in range(5)] for _ in range(l + 1)]

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

    print(min(dp[l]))
    
if __name__ == '__main__':
    main()

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

func = [lambda x: x,
        lambda x: 2 if x == 0 else int(x%2),
        lambda x: int(x%2==0),
        lambda x: 2 if x == 0 else int(x%2),
        lambda x: x]

before = [0]*5
for i in range(L):
    bmin = 1e10
    after = [0]*5
    for j in range(5):
        bmin = min(bmin, before[j])
        after[j] = bmin + func[j](A[i])
    before = after

print(min(before))

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

func = [lambda x: x,
        lambda x: 2 if x == 0 else int(x%2),
        lambda x: int(x%2==0),
        lambda x: 2 if x == 0 else int(x%2),
        lambda x: x]

before = [0]*5
for i in range(L):
    bmin = 1e10
    after = [0]*5
    for j in range(5):
        bmin = min(bmin, before[j])
        after[j] = bmin + func[j](A[i])
    before = after

print(min(before))

Solution (Python):
l = int(input())
a = []
for i in range(0, l):
    a.append(int(input()))

left = [0] * (l + 1)
start= [0] * (l + 1)
goal = [0] * (l + 1)
right = [0] * (l + 1)
last = [0] * (l + 1)

for i in range(1, l + 1):
    left[i] = left[i - 1] + a[i - 1]
    
for i in range(1, l + 1):
    c = 0
    if a[i - 1] == 0:
        c = 2
    elif a[i - 1] % 2 == 1:
        c = 1
    start[i] = min(left[i], start[i - 1] + c)

for i in range(1, l + 1):
    c = 0
    if a[i - 1] % 2 == 0:
        c = 1
    goal[i] = min(start[i], goal[i - 1] + c)
    
for i in range(1, l + 1):
    c = 0
    if a[i - 1] == 0:
        c = 2
    elif a[i - 1] % 2 == 1:
        c = 1
    right[i] = min(goal[i], right[i - 1] + c)
    
for i in range(1, l + 1):
    last[i] = min(last[i - 1] + a[i - 1], right[i])
    
print(last[-1])

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

dp = [[0 for i in range(5)] for j in range(l+1)]

def cost(s, a):
    if s == 0 or s == 4:
        return a
    elif s == 1 or s == 3:
        if a > 0:
            return a%2
        else:
            return 2
    else:
        return (a+1)%2

for i in range(l):
    dp[i+1][0] = min(dp[i][:1]) + cost(0, a[i])
    dp[i+1][1] = min(dp[i][:2]) + cost(1, a[i])
    dp[i+1][2] = min(dp[i][:3]) + cost(2, a[i])
    dp[i+1][3] = min(dp[i][:4]) + cost(3, a[i])
    dp[i+1][4] = min(dp[i][:5]) + cost(4, a[i])

print(min(dp[l]))

Solution (Python):

import sys
def 解():
    L=int(input())
    aA=[int(_) for _ in sys.stdin.readlines()]
    dp = [0]*5
    for i in range(L):
        i生 = aA[i]
        bA = i生 % 2
        i偶 = (2 if i生 == 0 else bA)
        i奇 = (1 if i生 == 0 else ( 0 if bA else 1) )
        dp[4] = min(dp[:]) + i生
        dp[3] = min(dp[:4]) + i偶
        dp[2] = min(dp[:3]) + i奇
        dp[1] = min(dp[:2]) + i偶
        dp[0] = dp[0] + i生
    print(min(dp))
解()

Solution (Python):
L = int(input())
aList = []
for _ in range(L):
    aList.append(int(input()))

dp = [0 for _ in range(5)]
for a in aList:
    outer = a % 2 if a > 0 else 2
    inner = (a + 1) % 2
    dp[4] = min(dp[:5]) + a
    dp[3] = min(dp[:4]) + outer
    dp[2] = min(dp[:3]) + inner
    dp[1] = min(dp[:2]) + outer
    dp[0] += a

print(min(dp))

Solution (Python):
N=int(input())
A=[int(input()) for i in range(N)]
B=[0]*N
for i in range(N):
    if A[i]>0:
        if A[i]%2==0:
            B[i]=2
        else:
            B[i]=1
L=[0,2,1,2,0]
dp=[[10**9]*5 for i in range(N+1)]
for k in range(5):
    dp[0][k]=0
for i in range(1,N+1):
    for k in range(5):
        for k1 in range(k+1):
            if 1<=k<=3:
                dp[i][k]=min(dp[i][k],dp[i-1][k1]+abs(L[k]-B[i-1]))
            else:
                dp[i][k]=min(dp[i][k],dp[i-1][k1]+A[i-1])
ans=10**9


for a in range(5):
    ans=min(ans,dp[N][a])
print(ans)

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

def cost(j,a):
    if(j == 0 or j == 4):
        return a
    elif(j == 1 or j == 3):
        if(a==0):
            return 2
        else:
            return a%2
    else:
        return (a+1)%2


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

print(min(DP[L]))

Solution (Python):
import sys
readline = sys.stdin.readline
L = int(input())
dp = [0] * 5
for a in map(int, (readline() for _ in range(L))):
    back = a % 2 if a > 0 else 2
    through = (a + 1) % 2
    dp[4] = min(dp[:5]) + a
    dp[3] = min(dp[:4]) + back
    dp[2] = min(dp[:3]) + through
    dp[1] = min(dp[:2]) + back
    dp[0] += a
print(min(dp))

Solution (Python):

import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def error_mat_print(m):
    for r in m:
        print(r, file=sys.stderr)

def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(L, A):

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

    for i, a in enumerate(A):
        t = dp[0][i]
        dp[0][i+1] = t + a
        t = min(t, dp[1][i])
        dp[1][i+1] = t+ ((a%2) if a != 0 else 2)
        t = min(t, dp[2][i])
        dp[2][i+1] = t + ((a+1)%2)
        t = min(t, dp[3][i])
        dp[3][i+1] =t + ((a%2) if a != 0 else 2)
        t = min(t, dp[4][i])
        dp[4][i+1] = t + a


    return min([dp[i][L] for i in range(5)])

def main():
    L = read_int()
    A = [read_int() for _ in range(L)]
    print(slv(L, A))


if __name__ == '__main__':
    main()

Solution (Python):

import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def error_mat_print(m):
    for r in m:
        print(r, file=sys.stderr)

def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(L, A):

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

    for i, a in enumerate(A):
        t = dp[0][i]
        dp[0][i+1] = t + a
        t = min(t, dp[1][i])
        dp[1][i+1] = t+ ((a%2) if a != 0 else 2)
        t = min(t, dp[2][i])
        dp[2][i+1] = t + ((a+1)%2)
        t = min(t, dp[3][i])
        dp[3][i+1] =t + ((a%2) if a != 0 else 2)
        t = min(t, dp[4][i])
        dp[4][i+1] = t + a


    return min([dp[i][L] for i in range(5)])

def main():
    L = read_int()
    A = [read_int() for _ in range(L)]
    print(slv(L, A))


if __name__ == '__main__':
    main()

Solution (Python):

import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def error_mat_print(m):
    for r in m:
        print(r, file=sys.stderr)

def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(L, A):

    dp = [[sys.maxsize] * (L+1) for _ in range(6)]
    for i in range(5):
        dp[i][0] = 0
    

    def s(a, t):
        if t == 0 or t == 4:
            return a
        if t == 1 or t == 3:
            if a == 0:
                return 2
            else:
                return a % 2
        else:
            return (a+1) % 2

    for i, a in enumerate(A):
        t = dp[0][i]
        dp[0][i+1] = t + a
        t = min(t, dp[1][i])
        dp[1][i+1] = t+ ((a%2) if a != 0 else 2)
        t = min(t, dp[2][i])
        dp[2][i+1] = t + ((a+1)%2)
        t = min(t, dp[3][i])
        dp[3][i+1] =t + ((a%2) if a != 0 else 2)
        t = min(t, dp[4][i])
        dp[4][i+1] = t + a

        
        

    return min([dp[i][L] for i in range(5)])

def main():
    L = read_int()
    A = [read_int() for _ in range(L)]
    print(slv(L, A))


if __name__ == '__main__':
    main()

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

Xs = [0, 2, 1, 2, 0]
dp = [[0]*(5) for _ in range(L+1)]
for i, A in enumerate(As, 1):
    A2 = 2 - A%2 if A > 2 else A
    for t, (X, A0) in enumerate(zip(Xs, [A, A2, A2, A2, A])):
        dp[i][t] = min(dp[i-1][:t+1]) + abs(A0-X)
print(min(dp[-1]))

Solution (Python):

import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(L, A):

    dp = [[sys.maxsize] * (L+1) for _ in range(5)]
    for i in range(5):
        dp[i][0] = 0

    def s(a, t):
        if t == 0 or t == 4:
            return a
        if t == 1 or t == 3:
            if a == 0:
                return 2
            else:
                return a % 2
        else:
            return (a+1) % 2

    for i, a in enumerate(A):
        for j in range(5):
            if j > 0:
                dp[j][i] = min(dp[j-1][i], dp[j][i])
            dp[j][i+1] = min(dp[j][i+1], dp[j][i]+s(a, j))
        
        
        
        
        
    

    return min([dp[i][L] for i in range(5)])

def main():
    L = read_int()
    A = [read_int() for _ in range(L)]
    print(slv(L, A))


if __name__ == '__main__':
    main()

Solution (Python):

l = int(input())
al = [int(input()) for _ in range(l)]
INF = 10**15
dp = [INF]*5  
dp[0] = 0

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

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

    
    
    
    
    
    

print(min(dp))

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


if __name__ == "__main__":
    main()

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

dp = [[float("inf")] * 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(L - 1):
    dp[i + 1][0] = dp[i][0] + A[i + 1]
    dp[i + 1][1] = min(dp[i][:2]) + A[i + 1] % 2 if A[i + 1] > 0 else min(dp[i][:2]) + 2
    dp[i + 1][2] = min(dp[i][:3]) + 1 - A[i + 1] % 2
    dp[i + 1][3] = min(dp[i][:4]) + A[i + 1] % 2 if A[i + 1] > 0 else min(dp[i][:4]) + 2
    dp[i + 1][4] = min(dp[i][:5]) + A[i + 1]
print min(dp[-1])

Solution (Python):




L = int(input())
DP = [0 for i in range(5)]

def cost(a):
    if a:
        return [a, a%2, (a+1)%2, a%2, a]
    else:
        return [0, 2, 1, 2, 0]

for i in range(L):
    n = [min(DP[:i+1]) for i in range(5)]
    cos = cost(int(input()))
    DP[4] = n[4] + cos[4]
    DP[3] = n[3] + cos[3]
    DP[2] = n[2] + cos[2]
    DP[1] = n[1] + cos[1]
    DP[0] = n[0] + cos[0]

print(min(DP))

Solution (Python):





L = int(input())

DP = [0 for i in range(5)]

def cost(a):
    if a:
        return [a, a%2, (a+1)%2, a%2, a]
    else:
        return [0, 2, 1, 2, 0]

def list_add(in1, in2):
    return [a + b for a, b in zip(in1, in2)]

for i in range(L):
    a = int(input())
    cos = cost(a)
    DP[4] = min(DP[:5]) + cos[4]
    DP[3] = min(DP[:4]) + cos[3]
    DP[2] = min(DP[:3]) + cos[2]
    DP[1] = min(DP[:2]) + cos[1]
    DP[0] = min(DP[:1]) + cos[0]



print(min(DP))

Solution (Python):





L = int(input())

DP = [0 for i in range(5)]

def cost(a):
    if a:
        return [a, a%2, (a+1)%2, a%2, a]
    else:
        return [0, 2, 1, 2, 0]

def list_add(in1, in2):
    return [a + b for a, b in zip(in1, in2)]

for i in range(L):
    n = [min(DP[:i+1]) for i in range(5)]
    a = int(input())
    cos = cost(a)
    DP = list_add(n, cos)



print(min(DP))

Solution (Python):





L = int(input())

DP = [0 for i in range(5)]

def cost(a):
    if a:
        return [a, a%2, (a+1)%2, a%2, a]
    else:
        return [0, 2, 1, 2, 0]

for i in range(L):
    n = [min(DP[:i+1]) for i in range(5)]
    a = int(input())
    cos = cost(a)
    DP[0] = n[0] + cos[0]
    DP[1] = n[1] + cos[1]
    DP[2] = n[2] + cos[2]
    DP[3] = n[3] + cos[3]
    DP[4] = n[4] + cos[4]



print(min(DP))

Solution (Python):





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

DP = [0 for i in range(5)]

def cost(s, a):
    if s == 0 or s == 4:
        return a
    elif s == 1 or s == 3:
        if a > 0:
            return a%2
        else:
            return 2
    else:
        return (a+1)%2

for i in range(L):
    n = [min(DP[:i+1]) for i in range(5)]
    a = A[i]
    DP[0] = n[0] + cost(0, a)
    DP[1] = n[1] + cost(1, a)
    DP[2] = n[2] + cost(2, a)
    DP[3] = n[3] + cost(3, a)
    DP[4] = n[4] + cost(4, a)



print(min(DP))

Solution (Python):





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

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

def cost(s, a):
    if s == 0 or s == 4:
        return a
    elif s == 1 or s == 3:
        if a > 0:
            return a%2
        else:
            return 2
    else:
        return (a+1)%2

for i in range(L):
    a = A[i]
    DP[i+1][0] = min(DP[i][:1]) + cost(0, a)
    DP[i+1][1] = min(DP[i][:2]) + cost(1, a)
    DP[i+1][2] = min(DP[i][:3]) + cost(2, a)
    DP[i+1][3] = min(DP[i][:4]) + cost(3, a)
    DP[i+1][4] = min(DP[i][:5]) + cost(4, a)



print(min(DP[L]))

Solution (Python):





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

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

def cost(s, a):
    if s == 0 or s == 4:
        return a
    elif s == 1 or s == 3:
        if a > 0:
            return a%2
        else:
            return 2
    else:
        return (a+1)%2

for i in range(L):
    DP[i+1][0] = min(DP[i][:1]) + cost(0, A[i])
    DP[i+1][1] = min(DP[i][:2]) + cost(1, A[i])
    DP[i+1][2] = min(DP[i][:3]) + cost(2, A[i])
    DP[i+1][3] = min(DP[i][:4]) + cost(3, A[i])
    DP[i+1][4] = min(DP[i][:5]) + cost(4, A[i])



print(min(DP[L]))

Solution (Python):





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

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

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

for i in range(L):
    DP[i+1][0] = min(DP[i][:1]) + cost(0, i, A[i])
    DP[i+1][1] = min(DP[i][:2]) + cost(1, i, A[i])
    DP[i+1][2] = min(DP[i][:3]) + cost(2, i, A[i])
    DP[i+1][3] = min(DP[i][:4]) + cost(3, i, A[i])
    DP[i+1][4] = min(DP[i][:5]) + cost(4, i, A[i])



print(min(DP[L]))

Solution (Python):





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

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

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):
    DP[i+1][0] = DP[i][0] + cost(0, i, A)
    DP[i+1][1] = min(DP[i][:2]) + cost(1, i, A)
    DP[i+1][2] = min(DP[i][:3]) + cost(2, i, A)
    DP[i+1][3] = min(DP[i][:4]) + cost(3, i, A)
    DP[i+1][4] = min(DP[i][:5]) + cost(4, i, A)



print(min(DP[L]))

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):
    DP[i+1][0] = DP[i][0] + cost(0, i, A)
    DP[i+1][1] = min(DP[i][:2]) + cost(1, i, A)
    DP[i+1][2] = min(DP[i][:3]) + cost(2, i, A)
    DP[i+1][3] = min(DP[i][:4]) + cost(3, i, A)
    DP[i+1][4] = min(DP[i][:5]) + cost(4, i, A)



print(min(DP[L]))

Solution (Python):
import sys
def f(j, a):
    if j == 2:
        return 1 - a%2
    if j % 2:
        return a % 2 if a else 2
    else:
        return a

L = int(input())
A = [0] + [int(sys.stdin.readline()) for _ in [0]*L]
B = [a%2 if a else 2 for a in A]
dp = [[0]*5 for _ in [0]*(L+1)]

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

Solution (Python):
import sys


def calc(itr):
    dp = [0]
    turn, no_turn, no_visit = 0, 0, 0
    for a in itr:
        b = a % 2
        new_turn = min(turn, no_visit) + (2 if a == 0 else b)
        new_no_turn = min(turn, no_turn, no_visit) + (b ^ 1)
        new_no_visit = no_visit + a
        dp.append(min(new_turn, new_no_turn, new_no_visit))
        turn, no_turn, no_visit = new_turn, new_no_turn, new_no_visit
    return dp


l = int(input())
aaa = list(map(int, sys.stdin))

dp_f = calc(aaa)
dp_b = calc(reversed(aaa))
dp_b.reverse()

print(min(map(sum, zip(dp_f, dp_b))))

Solution (Python):
n=int(input())
zot=lambda x:0 if x==0 else (x+1)%2+1
A=[int(input()) for i in range(n)]
D=[0,0,0,0,0]

for a in A:
  d0 = D[0] + a
  d1 = min(D[:2])+ [2,1,0][zot(a)]
  d2 = min(D[:3])+ [1,0,1][zot(a)]
  d3 = min(D[:4])+ [2,1,0][zot(a)]
  d4 = min(D) + a
  D=[d0,d1,d2,d3,d4]
print(min(D))

Solution (Python):


L = int(input())

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

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

for i in range(4):
    dp[i][0] = 0

for i in range(L):
    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)) + (1 if A[i] % 2 == 0 else 0)
    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(5)) + A[i]  


print(min(dp[i][L] for i in range(1, 5)))

Solution (Python):
L = int(input())
A = [int(input()) for _ in range(L)]
INF = 10**20
DP = [[INF for i in range(5)] for _ in range(L)]
DP[0][0] = A[0]
DP[0][1] = (2 if A[0] == 0 else 1 if A[0] % 2 == 1 else 0)
DP[0][2] = (1 if A[0] % 2 == 0 else 0)
DP[0][3] = (2 if A[0] == 0 else 1 if A[0] % 2 == 1 else 0)
DP[0][4] = A[0]

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

print(min(DP[L-1]))

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][:2]) + even
    
    dp[i+1][2] = min(dp[i][:3]) + odd
    
    dp[i+1][3] = min(dp[i][:4]) + even
    
    dp[i+1][4] = min(dp[i][:5]) + a
print(min(dp[L]))

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

dp = [0, 0, 0, 0, 0]
for a in A:
  cost24 = a % 2 if a > 0 else 2
  cost3 = int(a % 2 == 0)
  nextdp = []
  nextdp.append(dp[0] + a)
  nextdp.append(min(dp[:2]) + cost24)
  nextdp.append(min(dp[:3]) + cost3)
  nextdp.append(min(dp[:4]) + cost24)
  nextdp.append(min(dp) + a)
  dp = nextdp

print(min(dp))

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

INF = float('inf')
dp = [[INF]*5 for i in range(L+1)]
dp[0][0] = 0

for i,a in enumerate(A):
    cost_even = 2 if a==0 else a%2
    cost_odd = (a+1)%2

    dp[i+1][0] = min(dp[i+1][0], dp[i][0] + a)
    dp[i+1][1] = min(dp[i+1][1], dp[i][0] + cost_even)
    dp[i+1][2] = min(dp[i+1][2], dp[i][0] + cost_odd)
    dp[i+1][3] = min(dp[i+1][3], dp[i][0] + cost_even)
    dp[i+1][4] = min(dp[i+1][4], dp[i][0] + a)

    dp[i+1][1] = min(dp[i+1][1], dp[i][1] + cost_even)
    dp[i+1][2] = min(dp[i+1][2], dp[i][1] + cost_odd)
    dp[i+1][3] = min(dp[i+1][3], dp[i][1] + cost_even)
    dp[i+1][4] = min(dp[i+1][4], dp[i][1] + a)

    dp[i+1][2] = min(dp[i+1][2], dp[i][2] + cost_odd)
    dp[i+1][3] = min(dp[i+1][3], dp[i][2] + cost_even)
    dp[i+1][4] = min(dp[i+1][4], dp[i][2] + a)

    dp[i+1][3] = min(dp[i+1][3], dp[i][3] + cost_even)
    dp[i+1][4] = min(dp[i+1][4], dp[i][3] + a)

    dp[i+1][4] = min(dp[i+1][4], dp[i][4] + a)

print(min(dp[-1]))