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



Sample input:
4
1
0
2
3


Sample output:
1

Submission status: Wrong Answer

Solution code:
import sys
import copy
sys.setrecursionlimit(200000)
input = sys.stdin.readline
n = int(input())
a = [int(input()) for i in range(n)]
b = copy.deepcopy(a)
b = b[::-1]
c = copy.deepcopy(a)
zero = 0
nonzero = 0
x = 0
y= n
for i in range(n):
    if a[i] == 0:
        zero += 2
        if nonzero <= zero:
            zero = 0
            nonzero = 0
            x = i+1
    else:
        nonzero += a[i] - a[i] %2
zero = 0
nonzero = 0
for i in range(n-1,-1,-1):
    if a[i] == 0:
        zero += 1
        if nonzero <= zero:
            zero = 0
            nonzero = 0
            y = i
    else:
        nonzero += a[i] - (a[i]%2-1)*(-1)
ans = 0
for i in range(x):
    ans += a[i]
for i in range(y+1,n):
    ans += a[i]
for i in range(x,y):
    if a[i] == 0:
        a[i] = 0
        continue
    a[i] = a[i]%2+1
ki = 0
gu = 0
zero = 0
for i in range(x,y):
    if a[i] == 0:
        zero += 1
    elif a[i] == 1:
        gu += 1
    else:
        ki += 1
res = 1<<60
hki = 0
hgu = 0
hzero = 0
tmp = 0
for i in range(x,y):
    tmp = 0
    tmp =gu+zero+hki+hzero*2
    res = min(tmp,res)
    if a[i] == 0:
        zero -= 1
        hzero+=1
    elif a[i] == 1:
        gu -= 1
        hgu+=1
    else:
        ki -= 1
        hki+=1    
res = min(tmp,res)
a = b
kotae = ans+res
zero = 0
nonzero = 0
x = 0
y= n
for i in range(n):
    if a[i] == 0:
        zero += 2
        if nonzero <= zero:
            zero = 0
            nonzero = 0
            x = i+1
    else:
        zero = 0
        nonzero += a[i] - a[i] %2
zero = 0
nonzero = 0
for i in range(n-1,-1,-1):
    if a[i] == 0:
        zero += 1
        if nonzero <= zero:
            zero = 0
            nonzero = 0
            y = i
    else:
        nonzero += a[i] - (a[i]%2-1)*(-1)
ans = 0
for i in range(x):
    ans += a[i]
for i in range(y+1,n):
    ans += a[i]
for i in range(x,y):
    if a[i] == 0:
        a[i] = 0
        continue
    a[i] = a[i]%2+1
ki = 0
gu = 0
zero = 0
for i in range(x,y):
    if a[i] == 0:
        zero += 1
    elif a[i] == 1:
        gu += 1
    else:
        ki += 1
res = 1<<60
hki = 0
hgu = 0
hzero = 0
tmp = 0
for i in range(x,y):
    tmp = 0
    tmp =gu+zero+hki+hzero*2
    res = min(tmp,res)
    if a[i] == 0:
        zero -= 1
        hzero+=1
    elif a[i] == 1:
        gu -= 1
        hgu+=1
    else:
        ki -= 1
        hki+=1    
res = min(tmp,res)
kotae2 = res+ans

a = c
zero = 0
nonzero = 0
x = 0
y= n
for i in range(n):
    if a[i] == 0:
        zero += 2
        if nonzero <= zero:
            zero = 0
            nonzero = 0
            x = i+1
    else:
        zero = 0
        nonzero += a[i] - a[i] %2
zero = 0
nonzero = 0
for i in range(n-1,-1,-1):
    if a[i] == 0:
        zero += 2
        if nonzero <= zero:
            zero = 0
            nonzero = 0
            y = i
    else:
        nonzero += a[i] - a[i]%2
ans = 0
for i in range(x):
    ans += a[i]
for i in range(y+1,n):
    ans += a[i]
for i in range(x,y):
    if a[i] == 0:
        a[i] = 0
        continue
    a[i] = a[i]%2+1
ki = 0
gu = 0
zero = 0
for i in range(x,y):
    if a[i] == 0:
        zero += 1
    elif a[i] == 1:
        gu += 1
    else:
        ki += 1
res = 1<<60
hki = 0
hgu = 0
hzero = 0
tmp = 0
for i in range(x,y):
    tmp = 0
    tmp =ki+zero*2+hki+hzero*2
    res = min(tmp,res)
    if a[i] == 0:
        zero -= 1
        hzero+=1
    elif a[i] == 1:
        gu -= 1
        hgu+=1
    else:
        ki -= 1
        hki+=1    
res = min(tmp,res)
print(min(kotae,res+ans,kotae2))

Submission status: Wrong Answer

Solution code:
import sys
import copy
sys.setrecursionlimit(200000)
input = sys.stdin.readline
n = int(input())
a = [int(input()) for i in range(n)]
b = copy.deepcopy(a)
b = b[::-1]
c = copy.deepcopy(a)
zero = 0
nonzero = 0
x = 0
y= n
for i in range(n):
    if a[i] == 0:
        zero += 2
        if nonzero <= zero:
            zero = 0
            nonzero = 0
            x = i+1
    else:
        nonzero += a[i] - a[i] %2
zero = 0
nonzero = 0
for i in range(n-1,-1,-1):
    if a[i] == 0:
        zero += 1
        if nonzero <= zero:
            zero = 0
            nonzero = 0
            y = i
    else:
        nonzero += a[i] - (a[i]%2-1)*(-1)
ans = 0
for i in range(x):
    ans += a[i]
for i in range(y+1,n):
    ans += a[i]
for i in range(x,y):
    if a[i] == 0:
        a[i] = 0
        continue
    a[i] = a[i]%2+1
ki = 0
gu = 0
zero = 0
for i in range(x,y):
    if a[i] == 0:
        zero += 1
    elif a[i] == 1:
        gu += 1
    else:
        ki += 1
res = 1<<60
hki = 0
hgu = 0
hzero = 0
tmp = 0
for i in range(x,y):
    tmp = 0
    tmp =gu+zero+hki+hzero*2
    res = min(tmp,res)
    if a[i] == 0:
        zero -= 1
        hzero+=1
    elif a[i] == 1:
        gu -= 1
        hgu+=1
    else:
        ki -= 1
        hki+=1    
res = min(tmp,res)
a = b
kotae = ans+res
zero = 0
nonzero = 0
x = 0
y= n
for i in range(n):
    if a[i] == 0:
        zero += 2
        if nonzero <= zero:
            zero = 0
            nonzero = 0
            x = i+1
    else:
        zero = 0
        nonzero += a[i] - a[i] %2
zero = 0
nonzero = 0
for i in range(n-1,-1,-1):
    if a[i] == 0:
        zero += 1
        if nonzero <= zero:
            zero = 0
            nonzero = 0
            y = i
    else:
        nonzero += a[i] - (a[i]%2-1)*(-1)
ans = 0
for i in range(x):
    ans += a[i]
for i in range(y+1,n):
    ans += a[i]
for i in range(x,y):
    if a[i] == 0:
        a[i] = 0
        continue
    a[i] = a[i]%2+1
ki = 0
gu = 0
zero = 0
for i in range(x,y):
    if a[i] == 0:
        zero += 1
    elif a[i] == 1:
        gu += 1
    else:
        ki += 1
res = 1<<60
hki = 0
hgu = 0
hzero = 0
tmp = 0
for i in range(x,y):
    tmp = 0
    tmp =gu+zero+hki+hzero*2
    res = min(tmp,res)
    if a[i] == 0:
        zero -= 1
        hzero+=1
    elif a[i] == 1:
        gu -= 1
        hgu+=1
    else:
        ki -= 1
        hki+=1    
res = min(tmp,res)
kotae2 = res+ans

a = c
zero = 0
nonzero = 0
x = 0
y= n
for i in range(n):
    if a[i] == 0:
        zero += 2
        if nonzero <= zero:
            zero = 0
            nonzero = 0
            x = i+1
    else:
        zero = 0
        nonzero += a[i] - a[i] %2
zero = 0
nonzero = 0
for i in range(n-1,-1,-1):
    if a[i] == 0:
        zero += 1
        if nonzero <= zero:
            zero = 0
            nonzero = 0
            y = i
    else:
        nonzero += a[i] - a[i]%2
ans = 0
for i in range(x):
    ans += a[i]
for i in range(y+1,n):
    ans += a[i]
for i in range(x,y):
    if a[i] == 0:
        a[i] = 0
        continue
    a[i] = a[i]%2+1
ki = 0
gu = 0
zero = 0
for i in range(x,y):
    if a[i] == 0:
        zero += 1
    elif a[i] == 1:
        gu += 1
    else:
        ki += 1
res = 1<<60
hki = 0
hgu = 0
hzero = 0
tmp = 0
for i in range(x,y):
    tmp = 0
    tmp =ki+zero*2+hki+hzero*2
    res = min(tmp,res)
    if a[i] == 0:
        zero -= 1
        hzero+=1
    elif a[i] == 1:
        gu -= 1
        hgu+=1
    else:
        ki -= 1
        hki+=1    
res = min(tmp,res)
print(min(kotae,res+ans,kotae2))

Submission status: Wrong Answer

Solution code:
# 600 points
import copy

# -*- coding: utf-8 -*-
L = int(input())
b_row = []

res_min = 0

for _ in range(L):
    b_row.append(int(input()))

for k in range(L - 1):
    for j in range(k, L):

        row = copy.copy(b_row)

        for i in range(k, j+1):

            if i == j:
                row[i] = 0
            elif i == k:
                row[i] = row[i] % 2
            else:
                row[i] = (row[i] + 1) % 2

        if k == 0 and j == 1:
            res_min = sum(row)
        else:
            a = sum(row)
            if a < res_min:
                res_min = a

print(res_min)

Submission status: Wrong Answer

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

INF = 1E50
ans1 = sum(A)  # None
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],ans[0])
    tmp_ans[2]= min(ans[1],ans[2]+a_b_t[i])
    tmp_ans[3]= min(ans[2],ans[3]+a_alpha_t[i])
    tmp_ans[4] = min(ans[3]+a_alpha_t[i],ans[4]+A[i])
    ans = tmp_ans

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

Submission status: Wrong Answer

Solution code:

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], move_right[0] - no_left_sum[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], dp[-1][0]+abs(stone_diff[i]+1), dp[-1][1]+abs(stone_diff[i])-no_left_sum[i]) + no_left_sum[i+1])
        l.append(min(dp[-1][2], l[1] + move_right[i+1] - no_left_sum[i+1]))
        dp.append(l)
    return dp[-1][2]


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
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):
    if a[i] == 0:
        Reright.append(min(rightsum[i+1],2+Reright[-1]))
        Goright.append(min(rightsum[i+1],1+Goright[-1]))
    else:
        Reright.append(min(rightsum[i+1],a[i]%2+Reright[-1]))
        Goright.append(min(rightsum[i+1],(a[i]+1)%2+Goright[-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+Goleft[-1]))
    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+Goleft[-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))

Submission status: Wrong Answer

Solution code:
# coding: utf-8

"""

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回以下

zzoo
zzee
zzooee
zzeeoo
zzooeeoo xxx
zzeeooee
zz
???zz
"""

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

T = [L,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[6]+o),
    min(P[1]+e, P[6]+e),
    min(P[2]+e, P[0]+e),
    min(P[3]+o, P[1]+o),
    min(P[4]+o, P[2]+o),
    min(P[5]+e, P[3]+e),
    P[6]+a,
    min(P)+a,
  ]
  #print a, T
print min(T[4:]+T[5:])

Submission status: Wrong Answer

Solution code:
L = int(input())

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

checked = []
i = 0
score = 0
even_num = 0
zerocount = 0
before_even = False
double_even = False
while i < L:
    a = A[i]
    if a % 2 == 1:
        score += a
        i += 1
        before_even = False
    elif a == 0:
        while A[i] == 0:
            i += 1
            if i >= L:
                break
            zerocount += 1
        checked.append([score, zerocount, even_num, double_even])
        score = 0
        zerocount = 0
        even_num = 0
        before_even = False
        double_even = False
    else:
        if before_even:
            double_even = True
        score += a-1
        even_num += 1
        i += 1
        before_even = True
checked.append([score, 0, even_num, double_even])
now_s = 0
now_z = 0
now_e = 0
now_d = False
new = []
for score, zero, even_num, double_even in checked:
    now_s += score
    now_z += zero
    now_e += even_num
    now_d = now_d or double_even
    if now_s >= now_z:
        pass
    else:
        new.append([now_s, now_z, now_e, now_d])
        now_s = 0
        now_z = 0
        now_e = 0
        now_d = False
new.append([now_s, now_z, now_e, now_d])
# print(new)

ans = 0
max_i = 0
max_score = 0
for i, each in enumerate(new):
    s, z, e, d = each
    ans += s+e
    temp = s-z
    if d:
        temp += 1
    if e > 0:
        temp += 1
    if max_score <= temp:
        max_i = i
        max_score = temp
# print(ans)
ans -= max_score
print(ans)

Submission status: Wrong Answer

Solution code:
l=int(input())
a=[]
for k in range(l):
    t =int(input())
    if t == 0:
        a.append(t)
    else:
        a.append(t%2)
ans=9999
for i in range(l):
    for j in range(l):
        if i<j:
            for k in range(j-i+1):
                k+=i
                n=0
                m=0
                for t in range(k-i):
                    t+=i
                    if a[t] % 2 == 0:
                        n+=1
                    else:
                        m+=1
                for t in range(j-k+1):
                    t+=k
                    if a[t] % 2 == 0:
                        m+=1
                    else:
                        n+=1
                if ans>m:
                    ans=m
                if ans>n:
                    ans=n
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import copy
sys.setrecursionlimit(200000)
input = sys.stdin.readline
n = int(input())
a = [int(input()) for i in range(n)]
b = copy.deepcopy(a)
b = b[::-1]
zero = 0
nonzero = 0
x = 0
y= n
for i in range(n):
    if a[i] == 0:
        zero += 2
        if nonzero <= zero:
            zero = 0
            nonzero = 0
            x = i+1
    else:
        nonzero += a[i] - a[i] %2
zero = 0
nonzero = 0
for i in range(n-1,-1,-1):
    if a[i] == 0:
        zero += 1
        if nonzero <= zero:
            zero = 0
            nonzero = 0
            y = i
    else:
        nonzero += a[i] - (a[i]%2-1)*(-1)
ans = 0
for i in range(x):
    ans += a[i]
for i in range(y+1,n):
    ans += a[i]
for i in range(x,y):
    if a[i] == 0:
        a[i] = 0
        continue
    a[i] = a[i]%2+1
ki = 0
gu = 0
zero = 0
for i in range(x,y):
    if a[i] == 0:
        zero += 1
    elif a[i] == 1:
        gu += 1
    else:
        ki += 1
res = 1<<60
hki = 0
hgu = 0
hzero = 0
tmp = 0
for i in range(x,y):
    tmp = 0
    tmp =gu+zero+hki+hzero*2
    res = min(tmp,res)
    if a[i] == 0:
        zero -= 1
        hzero+=1
    elif a[i] == 1:
        gu -= 1
        hgu+=1
    else:
        ki -= 1
        hki+=1    
res = min(tmp,res)
a = b
kotae = ans+res
zero = 0
nonzero = 0
x = 0
y= n
for i in range(n):
    if a[i] == 0:
        zero += 2
        if nonzero <= zero:
            zero = 0
            nonzero = 0
            x = i+1
    else:
        nonzero += a[i] - a[i] %2
zero = 0
nonzero = 0
for i in range(n-1,-1,-1):
    if a[i] == 0:
        zero += 1
        if nonzero <= zero:
            zero = 0
            nonzero = 0
            y = i
    else:
        nonzero += a[i] - (a[i]%2-1)*(-1)
ans = 0
for i in range(x):
    ans += a[i]
for i in range(y+1,n):
    ans += a[i]
for i in range(x,y):
    if a[i] == 0:
        a[i] = 0
        continue
    a[i] = a[i]%2+1
ki = 0
gu = 0
zero = 0
for i in range(x,y):
    if a[i] == 0:
        zero += 1
    elif a[i] == 1:
        gu += 1
    else:
        ki += 1
res = 1<<60
hki = 0
hgu = 0
hzero = 0
tmp = 0
for i in range(x,y):
    tmp = 0
    tmp =gu+zero+hki+hzero*2
    res = min(tmp,res)
    if a[i] == 0:
        zero -= 1
        hzero+=1
    elif a[i] == 1:
        gu -= 1
        hgu+=1
    else:
        ki -= 1
        hki+=1    
res = min(tmp,res)
print(min(kotae,res+ans))

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(200000)
input = sys.stdin.readline
n = int(input())
a = [int(input()) for i in range(n)]
zero = 0
nonzero = 0
x = 0
y= n
for i in range(n):
    if a[i] == 0:
        zero += 2
        if nonzero <= zero:
            zero = 0
            nonzero = 0
            x = i+1
    else:
        nonzero += a[i] - a[i] %2
zero = 0
nonzero = 0
for i in range(n-1,-1,-1):
    if a[i] == 0:
        zero += 1
        if nonzero <= zero:
            zero = 0
            nonzero = 0
            y = i
    else:
        nonzero += a[i] - (a[i]%2-1)*(-1)
ans = 0
for i in range(x):
    ans += a[i]
for i in range(y+1,n):
    ans += a[i]
for i in range(x,y):
    if a[i] == 0:
        a[i] = 0
        continue
    a[i] = a[i]%2+1
ki = 0
gu = 0
zero = 0
for i in range(x,y):
    if a[i] == 0:
        zero += 1
    elif a[i] == 1:
        gu += 1
    else:
        ki += 1
res = 1<<60
hki = 0
hgu = 0
hzero = 0
tmp = 0
for i in range(x,y):
    tmp = 0
    tmp =gu+zero+hki+hzero*2
    res = min(tmp,res)
    if a[i] == 0:
        zero -= 1
        hzero+=1
    elif a[i] == 1:
        gu -= 1
        hgu+=1
    else:
        ki -= 1
        hki+=1    
res = min(tmp,res)
a = a[::-1]
kotae = ans+res
zero = 0
nonzero = 0
x = 0
y= n
for i in range(n):
    if a[i] == 0:
        zero += 2
        if nonzero <= zero:
            zero = 0
            nonzero = 0
            x = i+1
    else:
        nonzero += a[i] - a[i] %2
zero = 0
nonzero = 0
for i in range(n-1,-1,-1):
    if a[i] == 0:
        zero += 1
        if nonzero <= zero:
            zero = 0
            nonzero = 0
            y = i
    else:
        nonzero += a[i] - (a[i]%2-1)*(-1)
ans = 0
for i in range(x):
    ans += a[i]
for i in range(y+1,n):
    ans += a[i]
for i in range(x,y):
    if a[i] == 0:
        a[i] = 0
        continue
    a[i] = a[i]%2+1
ki = 0
gu = 0
zero = 0
for i in range(x,y):
    if a[i] == 0:
        zero += 1
    elif a[i] == 1:
        gu += 1
    else:
        ki += 1
res = 1<<60
hki = 0
hgu = 0
hzero = 0
tmp = 0
for i in range(x,y):
    tmp = 0
    tmp =ki+zero*2+hgu+hzero
    res = min(tmp,res)
    if a[i] == 0:
        zero -= 1
        hzero+=1
    elif a[i] == 1:
        gu -= 1
        hgu+=1
    else:
        ki -= 1
        hki+=1    
res = min(tmp,res)
print(min(kotae,res+ans))

Submission status: Wrong Answer

Solution code:
# coding: utf-8

"""

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回以下

zzoo
zzee
zzooee
zzeeoo
zzooeeoo
zzeeooee
zz
???zz
"""

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

T = [L,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[6]+o),
    min(P[1]+e, P[6]+e),
    min(P[2]+e, P[0]+e),
    min(P[3]+o, P[1]+o),
    min(P[4]+o, P[2]+o),
    min(P[5]+e, P[3]+e),
    P[6]+a,
    min(P)+a,
  ]
  #print a, T
print min(T)

Submission status: Wrong Answer

Solution code:
from itertools import accumulate
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

L = int(input())
l = [0]*L
l2 = [0]*L
for i in range(L):
    a = int(input())
    l[i] = a % 2

l = list(accumulate(l))
for i in range(L):
    l2[i] = abs(i+1-2*l[i])

ind = l2.index(max(l2))

ans = ind+1 - l[ind]+l[-1]-l[ind]
ans2 = l[ind] + L-ind-1 - l[-1]+l[ind]
print(min(ans, ans2))

Submission status: Wrong Answer

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

ans1 = 0
ans2 = 0
for i in range(N - 2):
  if A[i] % 2 == 0 and A[i + 1] % 2 == 1:
    ans1 += 1
  elif A[i] % 2 == 0 and A[i + 1] == 0:
    ans1 += 1
  elif A[i] == 0 and A[i + 1] % 2 == 1:
    ans1 += 1
  if A[i] % 2 == 1 and A[i + 1] % 2 == 0:
    ans2 += 1
  elif A[i] == 0 and A[i + 1] % 2 == 0:
    ans2 += 1
  elif A[i] % 2 == 1 and A[i] == 0:
    ans2 +=1
print(min(ans1,ans2))

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(200000)
input = sys.stdin.readline
n = int(input())
a = [int(input()) for i in range(n)]
zero = 0
nonzero = 0
x = 0
y= n
for i in range(n):
    if a[i] == 0:
        zero += 1
        if nonzero <= zero:
            zero = 0
            nonzero = 0
            x = i+1
    else:
        nonzero += a[i]
zero = 0
nonzero = 0
for i in range(n-1,-1,-1):
    if a[i] == 0:
        zero += 1
        if nonzero <= zero:
            zero = 0
            nonzero = 0
            y = i
    else:
        nonzero += a[i]
ans = 0
for i in range(x):
    ans += a[i]
for i in range(y+1,n):
    ans += a[i]
for i in range(x,y):
    if a[i] == 0:
        a[i] = 0
        continue
    a[i] = a[i]%2+1
ki = 0
gu = 0
zero = 0
for i in range(x,y):
    if a[i] == 0:
        zero += 1
    elif a[i] == 1:
        gu += 1
    else:
        ki += 1
res = 1<<60
hki = 0
hgu = 0
hzero = 0
tmp = 0
for i in range(x,y):
    tmp = 0
    tmp = min(gu+zero+hki+hzero*2,ki+zero*2+hgu+hzero)
#    print(tmp,ki,gu,zero)
    res = min(tmp,res)
    if a[i] == 0:
        zero -= 1
        hzero+=1
    elif a[i] == 1:
        gu -= 1
        hgu+=1
    else:
        ki -= 1
        hki+=1    
res = min(tmp,res)
print(ans+res)

Submission status: Wrong Answer

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

INF = 10 ** 20

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[state][i + 1], dp[state][i] + aList[i])
        elif state == 3:
            dp[state][i + 1] = min(dp[state][i + 1], dp[state][i] + (aList[i] % 2 if aList[i] != 0 else 2))
            dp[state + 1][i + 1] = min(dp[state + 1][i + 1], dp[state][i] + aList[i])
        elif state == 2:
            dp[state][i + 1] = min(dp[state][i + 1], dp[state][i] + (aList[i] - 1) % 2)
            dp[state + 1][i + 1] = min(dp[state + 1][i + 1], dp[state][i] + (aList[i] % 2 if aList[i] != 0 else 2))
        elif state == 1:
            dp[state][i + 1] = min(dp[state][i + 1], dp[state][i] + (aList[i] % 2 if aList[i] != 0 else 2))
            dp[state + 1][i + 1] = min(dp[state + 1][i + 1], dp[state][i] + (aList[i] - 1) % 2)

        else:
            dp[state][i + 1] = min(dp[state][i + 1], dp[state][i] + aList[i])
            dp[state + 1][i + 1] = min(dp[state + 1][i + 1], dp[state][i] + (aList[i] % 2 if aList[i] != 0 else 2))

ans = INF
for i in range(5):
    ans = min(ans, dp[i][l])
print(ans)

Submission status: Wrong Answer

Solution code:
# coding: utf-8

"""

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回以下

zzoo
zzee
zzooee
zzeeoo
zzooeeoo
zzeeooee
zz
???zz
"""

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

o = 1-A[0]%2
e = 1-o
if A[0]==0:
  e = 2
T = [o,e,L,L,L,L,A[0],L]

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

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(200000)
input = sys.stdin.readline
n = int(input())
a = [int(input()) for i in range(n)]
zero = 0
nonzero = 0
x = 0
y= n
for i in range(n):
    if a[i] == 0:
        zero += 1
        if nonzero <= zero:
            zero = 0
            nonzero = 0
            x = i+1
    else:
        nonzero += a[i]-1
zero = 0
nonzero = 0
for i in range(n-1,-1,-1):
    if a[i] == 0:
        zero += 1
        if nonzero <= zero:
            zero = 0
            nonzero = 0
            y = i
    else:
        nonzero += a[i]-1
ans = 0
for i in range(x):
    ans += a[i]
for i in range(y+1,n):
    ans += a[i]
for i in range(x,y):
    if a[i] == 0:
        a[i] = 0
        continue
    a[i] = a[i]%2+1
ki = 0
gu = 0
zero = 0
for i in range(x,y):
    if a[i] == 0:
        zero += 1
    elif a[i] == 1:
        gu += 1
    else:
        ki += 1
res = 1<<60
hki = 0
hgu = 0
hzero = 0
tmp = 0
for i in range(x,y):
    tmp = 0
    tmp = min(gu+zero+hki+hzero*2,ki+zero*2+hgu+hzero)
#    print(tmp,ki,gu,zero)
    res = min(tmp,res)
    if a[i] == 0:
        zero -= 1
        hzero+=1
    elif a[i] == 1:
        gu -= 1
        hgu+=1
    else:
        ki -= 1
        hki+=1    
res = min(tmp,res)
print(ans+res)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys, os
try: from typing import Any, Union, List, Tuple, Dict
except ImportError: pass
sys.setrecursionlimit(10**6)
if os.environ.get("USER") == "shun":
    def debug(*args): print(*args, file=sys.stderr)
else:
    print("NO DEBUG", file=sys.stderr)
    def debug(*args): pass
def exit(): sys.exit(0)


l = int(input())
a = []
for _ in range(l):
    a.append(int(input()))

init_score = 0
for i in range(l):
    if a[i] == 0:
        init_score += 2
    elif a[i] % 2 == 0:
        pass
    else:
        init_score += 1

left = [0]
for i in range(l):
    left.append(left[i])
    if a[i] == 0:
        left[i+1] -= 2
    elif a[i] % 2 == 0:
        left[i+1] += a[i]
    else:
        left[i+1] += a[i] - 1
left_i = 0
left_min = left[0]
for i in range(l+1):
    if left[i] < left_min:
        left_i = i
        left_min = left[i]
debug(left_i, left)

right = [0] * (l+1)
for i in range(l, 0, -1):
    right[i-1] = right[i]
    if a[i-1] == 0:
        right[i-1] -= 2
    elif a[i-1] % 2 == 0:
        right[i-1] += a[i-1]
    else:
        right[i-1] += a[i-1] - 1
right_i = 0
right_min = right[0]
for i in range(l+1):
    if right[i] < right_min:
        right_i = i
        right_min = right[i]
debug(right_i, right)


# odd
temp_score = init_score + left_min + right_min
b = a[left_i:right_i]
k = len(b)

for i in range(k):
    if b[i] == 0:
        temp_score -= 1
    elif b[i] % 2 == 0:
        temp_score += 1
    else:
        temp_score -= 1


left = [0]
for i in range(k):
    left.append(left[i])
    if b[i] == 0:
        left[i+1] += 1
    elif b[i] % 2 == 0:
        left[i+1] -= 1
    else:
        left[i+1] += 1
left_i = 0
left_min = left[0]
for i in range(k+1):
    if left[i] < left_min:
        left_i = i
        left_min = left[i]
debug(left_i, left)

right = [0] * (k+1)
for i in range(k, 0, -1):
    right[i-1] = right[i]
    if b[i-1] == 0:
        right[i-1] += 1
    elif b[i-1] % 2 == 0:
        right[i-1] -= 1
    else:
        right[i-1] += 1
right_i = 0
right_min = right[0]
for i in range(k+1):
    if right[i] < right_min:
        right_i = i
        right_min = right[i]
debug(right_i, right)

score = temp_score + left_min + right_min
print(score)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(200000)
input = sys.stdin.readline
n = int(input())
a = [int(input()) for i in range(n)]
zero = 0
nonzero = 0
x = 0
y= n
for i in range(n):
    if a[i] == 0:
        zero += 1
        if nonzero <= zero:
            zero = 0
            nonzero = 0
            x = i+1
    else:
        nonzero += a[i]-1
for i in range(n-1,-1,-1):
    if a[i] == 0:
        zero += 1
        if nonzero <= zero:
            zero = 0
            nonzero = 0
            y = i
    else:
        nonzero += a[i]-1
ans = 0
for i in range(x):
    ans += a[i]
for i in range(y+1,n):
    ans += a[i]
for i in range(x,y):
    if a[i] == 0:
        a[i] = 0
        continue
    a[i] = a[i]%2+1
ki = 0
gu = 0
zero = 0
for i in range(x,y):
    if a[i] == 0:
        zero += 1
    elif a[i] == 1:
        gu += 1
    else:
        ki += 1
res = 1<<60
hki = 0
hgu = 0
hzero = 0
tmp = 0
for i in range(x,y):
    tmp = 0
    tmp = min(gu+zero+hki+hzero*2,ki+zero*2+hgu+hzero)
#    print(tmp,ki,gu,zero)
    res = min(tmp,res)
    if a[i] == 0:
        zero -= 1
        hzero+=1
    elif a[i] == 1:
        gu -= 1
        hgu+=1
    else:
        ki -= 1
        hki+=1    
res = min(tmp,res)
print(ans+res)

Submission status: Wrong Answer

Solution code:
# coding: utf-8

"""

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回以下

zzoo
zzee
zzooee
zzeeoo
zzooeeoo
zzeeooee
zz
???zz
"""

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

if A[0]==0:
  T = [1,2,L,L,L,L,0,L]
else:
  if A[0]%2==0:
    T = [1,0,L,L,L,L,A[0],L]
  else:
    T = [0,1,L,L,L,L,A[0],L]

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

Submission status: Wrong Answer

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

ans = 0
for i in range(N - 2):
  if A[i] % 2 == 0 and A[i + 1] % 2 == 1:
    ans += 1
  elif A[i] % 2 == 0 and A[i + 1] == 0:
    ans += 1
  elif A[i] == 0 and A[i + 1] % 2 == 1:
    ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
l = int(input())
a = []
for i in range(l):
  a.append(int(input()))
if len(a) == len(set(a)):
  print(1)
else:
  print(len(a)-len(set(a)))