Submission #62279213

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def solve():
    N=int(input())
    A=input().strip()
    n3=3**N
    bits=[0]*n3
    for i,c in enumerate(A):
        bits[i]=0 if c=='0' else 1
    B=bits[:]
    length=n3
    for _ in range(N):
        new_length=length//3
        newB=[0]*new_length
        idx=0
        for i in range(new_length):
            s=B[idx]+B[idx+1]+B[idx+2]
            newB[i]=1 if s>=2 else 0
            idx+=3
        B=newB
        length=new_length
    final_bit=B[0]
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

def solve():
    N=int(input())
    A=input().strip()
    n3=3**N
    bits=[0]*n3
    for i,c in enumerate(A):
        bits[i]=0 if c=='0' else 1
    B=bits[:]
    length=n3
    for _ in range(N):
        new_length=length//3
        newB=[0]*new_length
        idx=0
        for i in range(new_length):
            s=B[idx]+B[idx+1]+B[idx+2]
            newB[i]=1 if s>=2 else 0
            idx+=3
        B=newB
        length=new_length
    final_bit=B[0]

    cost0=[0]*n3
    cost1=[0]*n3
    for i in range(n3):
        if bits[i]==0:
            cost0[i]=0
            cost1[i]=1
        else:
            cost0[i]=1
            cost1[i]=0

    length=n3
    for _ in range(N):
        new_length=length//3
        new_cost0=[0]*new_length
        new_cost1=[0]*new_length
        idx=0
        for i in range(new_length):
            c0_0=cost0[idx]
            c0_1=cost0[idx+1]
            c0_2=cost0[idx+2]
            c1_0=cost1[idx]
            c1_1=cost1[idx+1]
            c1_2=cost1[idx+2]

            s00=c0_0+c0_1+c0_2
            s01=c0_0+c0_1+c1_2
            s02=c0_0+c1_1+c0_2
            s03=c1_0+c0_1+c0_2
            new_cost0[i]=min(s00,s01,s02,s03)

            s10=c1_0+c1_1+c1_2
            s11=c1_0+c1_1+c0_2
            s12=c1_0+c0_1+c1_2
            s13=c0_0+c1_1+c1_2
            new_cost1[i]=min(s10,s11,s12,s13)

            idx+=3

        cost0, cost1=new_cost0, new_cost1
        length=new_length


    if final_bit==0:
        print(cost1[0])
    else:
        print(cost0[0])



solve()

Submission Info

Judge Result