Problem:


Score : 700 points

Problem Statement

Given is a sequence of N digits a_1a_2\ldots a_N, where each element is 1, 2, or 3.
Let x_{i,j} defined as follows:

x_{1,j} := a_j \quad (1 \leq j \leq N)

x_{i,j} := | x_{i-1,j} - x_{i-1,j+1} | \quad (2 \leq i \leq N and 1 \leq j \leq N+1-i)

Find x_{N,1}.

Constraints

2 \leq N \leq 10^6

a_i = 1,2,3 (1 \leq i \leq N)

Input

Input is given from Standard Input in the following format:

N
a_1a_2\ldotsa_N

Output

Print x_{N,1}.

Sample Input 1

4
1231

Sample Output 1

1

x_{1,1},x_{1,2},x_{1,3},x_{1,4} are respectively 1,2,3,1.

x_{2,1},x_{2,2},x_{2,3} are respectively |1-2| = 1,|2-3| = 1,|3-1| = 2.

x_{3,1},x_{3,2} are respectively |1-1| = 0,|1-2| = 1.

Finally, x_{4,1} = |0-1| = 1, so the answer is 1.

Sample Input 2

10
2311312312

Sample Output 2

0



Sample input:
4
1231


Sample output:
1

Submission status: Wrong Answer

Solution code:
import math
N = int(input())
a = input()

def combination(n: int, r: int) -> int:
    comb = 1
    for i in range(r):
        comb *= n-i
    comb //= math.factorial(r)
    return comb

def is_ans_odd(a: str) -> bool:
    co_mod2 = 0
    for i, c in enumerate(a):
        x = int(c)
        co = combination(len(a)-1, i)
        co_mod2 += x*co
        co_mod2 %= 2

    is_odd = True
    if co_mod2 == 0:
        is_odd = False

    return is_odd

def main():
    ans = -1
    table = str.maketrans({'1': '0', '2': '1', '3': '2'})
    a012 = a.translate(table)
    if is_ans_odd(a012):
        ans = 1
    else:
        if '1' in a012:
            ans = 0
        else:
            table = str.maketrans({'2': '0'})
            a01 = a012.translate(table)
            if is_ans_odd(a01):
                ans = 2
            else:
                ans = 0

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import math
N = int(input())
a = input()

def combination(n: int, r: int) -> int:
    return math.factorial(n) // math.factorial(n-r) // math.factorial(r)

def is_ans_odd(a: str) -> bool:
    co_mod2 = 0
    for i, c in enumerate(a):
        x = int(c)
        co = combination(len(a)-1, i)
        co_mod2 += x*co
        co_mod2 %= 2

    is_odd = True
    if co_mod2 == 0:
        is_odd = False

    return is_odd

def main():
    ans = -1
    table = str.maketrans({'1': '0', '2': '1', '3': '2'})
    a012 = a.translate(table)
    if is_ans_odd(a012):
        ans = 1
    else:
        if '1' in a012:
            ans = 0
        else:
            table = str.maketrans({'2': '0'})
            a01 = a012.translate(table)
            if is_ans_odd(a01):
                ans = 2
            else:
                ans = 0

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())
A = input()

S = [int(A[i])-1 for i in range(N)]
oddness = 0
for i in range(N):
  m, n = N-1, i
  if S[i] % 2 != 0:
    parity = 1
    while m != 0:
      if m % 2 == 0 and n % 2 == 1:
        parity = 0
        break
      m //= 2
      n //= 2
    oddness += parity
    oddness %= 2

if oddness == 1:
  print(1)
else:
  if 1 in S:
    print(0)
  else:
    S = [S[i]//2 for i in range(N)]
    oddness = 0
    for i in range(N-1):
      m, n = N-1, i+1
      if S[i] % 2 != 0:
        parity = 1
        while m != 0:
          if m % 2 == 0 and n % 2 == 1:
            parity = 0
            break
          m //= 2
          n //= 2
        oddness += parity
        oddness %= 2
    if oddness == 1:
      print(2)
    else:
      print(0)

Submission status: Wrong Answer

Solution code:
#editorial参照

#偶奇
import numpy as np
n=int(input())
a_ = list(map(int, list(input())))
a = np.array(a_)
div2=[1]
cnt=0
ex1 = False

if 1 in a:
    ex1 = True
else:
    a//=2
for i in range(1,n):
    cnt += bin(n-i)[::-1].find('1')
    cnt -= bin(i)[::-1].find('1')
    div2.append(cnt)

div2=np.array(div2)

tmp= (a*div2%2).sum()%2
if tmp:
    if ex1:
        print(1)
    else:
        print(2)

else:
    print(0)

Submission status: Wrong Answer

Solution code:
#editorial参照

import numpy as np
n=int(input())
a_ = list(map(int, list(input())))
a = np.array(a_)
div2=[1]
cnt=0
ex1 = False
#02のみのケースを前処理
if 1 in a:
    ex1 = True
else:
    a//=2
#偶奇
for i in range(1,n):
    cnt += bin(n-i).find('1')
    cnt-= bin(i).find('1')
    div2.append(cnt)

div2=np.array(div2)

tmp= (a*div2%2).sum()%2
if tmp:
    if ex1:
        print(1)
    else:
        print(2)

else:
    print(0)

Submission status: Wrong Answer

Solution code:
N = int(input())
an = [int(x) for x in list(input())]

while len(an) > 1:

    for i in range(len(an)-1):
        an[i] = abs(an[i]-an[i+1])
        pass
        
    an = [x for x in an if not x == 0]
    an = an[:-1]
        
if len(an)==0:
    print(0)
else:
    print(an[0])

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Mar 21 20:58:03 2020

@author: naoki
"""

#f = open("C:/Users/naoki/Desktop/Atcoder/input.txt")
N = int(input())
a = list(map(int, list(input())))

flag1 = [-100, -100]
flag2 = [-100, -100]
flag3 = [-100, -100]

for i in range(N//2):
    if a[i] == 2:
        flag1[0] = i
    if a[N-i-1] ==2 :
        flag1[1] = N-i-1
    if (a[i] == 1 and a[i+1] == 3) or (a[i] == 3 and a[i+1] == 1):
        flag2[0] = i
    if (a[N-i-1] == 1 and a[N-i-2] == 3) or (a[N-i-1] == 3 and a[N-i-2] == 1):
        flag2[1] = N-i-1
    
    if flag1[0] >= 0 and flag1[1] >= 0:
        b = []
        b.extend(a[0:flag1[0]+1])
        b.extend(a[flag1[1]:])
        break
    if flag2[0] >= 0 and flag2[1] >= 0:
        b = [] 
        b.extend(a[0:flag2[0]+1])
        b.extend(a[flag2[1]-1:])
        break
else:
    b = a
last = []
if b[0] != b[1]:
    last.append(b[0])
for i in range(len(b)-1):
    if b[i] != b[i+1]:
        last.append(b[i+1])

for i in range(len(last)-1):
    for p in range(len(last)-i-1):
        last[p] = abs(last[p+1] - last[p])
if len(last)>0:
    print(last[0])
else: 
    print(0)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = input()
MAX = 10 ** 6

comb = [1] * (n + 1)
for i in range(1, n + 1):
    comb[i] = comb[i-1] * (n - i) // i

ans = 0
for i, e in enumerate(a, 1):
    e = int(e) - 1
    ans += e * comb[i]
    ans %= 3

if ans % 2 and "2" in a:
    ans = 0

print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
A=[int(a)-1 for a in input()]
r=1-(1 in A)
print(sum([A[i]&r and (N-1&i)==i for i in range(N)])%2*r)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = lambda x: int(x)-1
A = list(map(a, input().split()))
cnt = 0
n1 = n - 1
def cmb(x, y):
    y = min(y, x-y)
    for i in range(x-y+1, x+1):
        ans *= i
    for i in range(1, y+1):
        ans //= i
    return ans
for i, a in enumerate(A, 1):
    if a == 1:
        cnt += cmb(n1, i)
if cnt%2==1:
    print(1)
elif cnt > 0:
    print(0)
else:
    AA = [a//2 for a in A]
    cnt = 0
    for i, a in enumerate(AA, 1):
        if a == 1:
            cnt += cmb(n1, i)
    if cnt%2:
        print(2)
    else:
        print(0)

Submission status: Wrong Answer

Solution code:
from functools import reduce
n = int(input())
A = list(map(int, input().split()))
cnt = 0
n1 = n - 1
mul = lambda x, y: x*y
def cmb(x, y):
    y = min(y, x-y)
    over = reduce(mul, range(x-y+1, x+1))
    under = reduce(mul, range(1, y+1))
    return over//under
for i, a in enumerate(A, 1):
    if a == 2:
        cnt += cmb(n1, i)
if cnt%2==1:
    print(1)
elif cnt > 0:
    print(0)
else:
    AA = [(a-1)//2 for a in A]
    cnt = 0
    for i, a in enumerate(AA, 1):
        if a == 1:
            cnt += cmb(n1, i)
    if cnt%2:
        print(2)
    else:
        print(0)

Submission status: Wrong Answer

Solution code:
import numpy as np
N = int(input())
A = [int(s)-1 for s in input()]
#print(A)
if 1 in A:
  factor = 1
else:
  factor = 2
  A = [a//2 for a in A]

n = len(A) - 1
s = 0
for i, a in enumerate(A):
  s += a * (n == ( i | (n - i) )) 
print(s%2)

Submission status: Wrong Answer

Solution code:
import numpy as np
N = int(input())
A = [int(s)-1 for s in input()]
#print(A)
if 1 in A:
  factor = 1
else:
  factor = 2
  A = [a/2 for a in A]

n = len(A) - 1
s = 0
for i, a in enumerate(A):
  s += a * (n == ( i | (n - i) )) 
print(factor * (s%2))

Submission status: Wrong Answer

Solution code:
import numpy as np
N = int(input())
A = [int(s)-1 for s in input()]
#print(A)
if 1 in A:
  factor = 1
else:
  factor = 2
  A = [a/2 for a in A]

n = len(A) - 1
s = 0
for i, a in enumerate(A):
  s += a * (n == ( i | (n - i) )) 
print(s%2)

Submission status: Wrong Answer

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

def solve(N: int, a: str):
    a = [int(a[i])-1 for i in range(N)]
    zeroone = [a[i]&1 for i in range(N)]

    SUM = 0

    comb = [0]*N
    comb[0] = 1

    for i in range(1, N):
        comb[i] = 1 if (N-1)&i == i else 0

    for i in range(N):
        SUM += zeroone[i]*comb[i]
    SUM %= 2

    if SUM == 1:
        print(1)
        return
    
    for i in range(N):
        if a[i] == 1:
            print(0)
            return
    
    ## 0か2
    zerotwo = [a[i]//2 for i in range(N)]

    SUM = 0
    for i in range(1,N):
        SUM += zerotwo[i]*comb[i]

    SUM %= 2

    if SUM == 1:
        print(2)
        return
    
    print(0)
    return


def main():
    N = int(input())  # type: int
    a = input() 
    solve(N, a)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())
A = [int(a)-1 for a in input()]

if A.count(1) == 0:
    r = 2
else:
    r = 1

def parity_of_binominal_coefficient(n, k):
    return (n&k)==k

for i, a in enumerate(A):
    ans = 1
    if a & 1:
        if not parity_of_binominal_coefficient(N-1,i):
            ans ^= 1

print(ans*r)

Submission status: Wrong Answer

Solution code:
N = int(input())
a = list(map(int,list(input())))
a = list(map(lambda x:x-1,a))
x = 0
num_mod = [0]*N
for i in range(1,N):
  tmp = 0
  while i%2==0:
    i//=2
    tmp+=1
  num_mod[i] = num_mod[i-1]+tmp
  

for i,n in enumerate(a):
  if n%2==0:
    continue
  else:
    if num_mod[N-1]==(num_mod[i]+num_mod[N-1-i]):
      x+=1

if x%2!=0:
  print(1)
  
elif 1 in a:
  print(0)

else:
  a = [x//2 for x in a]
  x = 0
  for i,n in enumerate(a):
    if n%2==0:
      continue
    else:
      if num_mod[N-1]==(num_mod[i]+num_mod[N-1-i]):
        x+=1
  if x%2!=0:
    print(2)
  else:
    print(0)

Submission status: Wrong Answer

Solution code:
N = int(input())
a = list(map(int,list(input())))
a = list(map(lambda x:x-1,a))
x = 0
num_mod = [0]*N
for i in range(1,N):
  tmp = 0
  while i%2==0:
    i//=2
    tmp+=1
  num_mod[i] = num_mod[i-1]+x
  

for i,n in enumerate(a):
  if n%2==0:
    continue
  else:
    if num_mod[N-1]==(num_mod[i]+num_mod[N-1-i]):
      x+=1

if x%2!=0:
  print(1)
  
elif 1 in a:
  print(0)

else:
  a = [x//2 for x in a]
  x = 0
  for i,n in enumerate(a):
    if n%2==0:
      continue
    else:
      if num_mod[N-1]==(num_mod[i]+num_mod[N-1-i]):
        x+=1
  if x%2!=0:
    print(2)
  else:
    print(0)

Submission status: Wrong Answer

Solution code:
N = int(input())
a = list(map(int,list(input())))
a = list(map(lambda x:x-1,a))
x = 0
num_mod = [0]*N
for i in range(1,N):
  x = 0
  while i%2==0:
    i//=2
    x+=1
  num_mod[i] = num_mod[i-1]+x
  

for i,n in enumerate(a):
  if n%2==0:
    continue
  else:
    if num_mod[N-1]==(num_mod[i]+num_mod[N-1-i]):
      x+=1

if x%2!=0:
  print(1)
  
elif 1 in a:
  print(0)

else:
  a = [x//2 for x in a]
  x = 0
  for i,n in enumerate(a):
    if n%2==0:
      continue
    else:
      if num_mod[N-1]==(num_mod[i]+num_mod[N-1-i]):
        x+=1
  if x%2!=0:
    print(2)
  else:
    print(0)

Submission status: Wrong Answer

Solution code:
def nCk(n, k):
    if n&k == k:
        return 1
    else:
        return 0

n = int(input())
a = list(map(int, list(input())))
ans = 0
cnt = 0
for i in range(n):
    a[i] -= 1
    if a[i] % 2 == 1:
        ans += nCk(n-1, i) % 2
        cnt = 1
if ans % 2 == 1:
    print(1)
else:
    if cnt == 1:
        print(0)
    else:
        print(2)

Submission status: Wrong Answer

Solution code:
N = int(input())
a = list(map(int,list(input())))
a = list(map(lambda x:x-1,a))
x = 0
for i,n in enumerate(a):
  if n%2==0:
    continue
  else:
    if ((N-1)^i)&i==0:
      x+=1

if x%2!=0:
  print(1)
  
elif 1 in a:
  print(0)

else:
  print(2)

Submission status: Wrong Answer

Solution code:
N = int(input())
a = list(map(int,list(input())))
a = list(map(lambda x:x-1,a))
x = 0
for i,n in enumerate(a):
  if n%2==0:
    continue
  else:
    if ((N-1)^i)&i==0:
      x+=1

if x%2!=0:
  print(1)
  
elif 1 in a:
  print(0)

Submission status: Wrong Answer

Solution code:
N = int(input())
a = list(map(int,list(input())))
a = list(map(lambda x:x-1,a))
x = 0
for i,n in enumerate(a):
  if n%2==0:
    continue
  else:
    if ((N-1)^i)&i==0:
      x+=1

if x%2!=0:
  print(1)
  
if 1 in a:
  print(0)

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,list(input())))

H=[]
for j in range(len(A)-1):
    H.append(abs(A[j]-A[j+1]))

count=[0,0,0]
for x in H:
    count[x]+=1

if count[1]==0:
    print(H[0]^H[-1])
else:
    if H[0]==2:
        H[0]=0
    if H[-1]==2:
        H[-1]=0
    print(H[0]^H[-1])

Submission status: Wrong Answer

Solution code:
N = int(input())
a = list(map(int, list(input())))

while len(a) != 1:
	inx = 1 << (len(bin(N - 1)) - 3)

	N -= inx
	x = [0] * N
	for i in range(N):
		x[i] = abs(a[i] - a[i + inx])

	a = x

print(a[0])

Submission status: Wrong Answer

Solution code:
N = int(input())
a = list(map(int,list(input())))
a = list(map(lambda x:x-1,a))
x = 0
for i,n in enumerate(a):
  if n%2==0:
    continue
  else:
    if ((N-1)^i)&i==0:
      x+=1
      
if x%2!=0:
  print(1)

Submission status: Wrong Answer

Solution code:
import math
import sys

stdin = sys.stdin

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))
mod = 10**9 + 7 
sys.setrecursionlimit(1000010)

N = ni()
S  = ns()
# print(N,S)


def combMod2(n):
    if n==0: 
        return [1]
    elif n==1:
        return [1,1]
    s=2
    i=1
    while n>=s:
        i = i +1 
        s = s * 2
    s = s//2
    i = i -1
    k = n -s 
    # print(n,n+1,k+1 , s-k-1 ,k+1, s,i)
    ret = []
    ret.extend(combMod2(k))
    ret.extend([0]*(s-k-1))
    ret.extend(combMod2(k))
    return ret

u = combMod2(N-1)
#print(u)
ans = 0 
for i in range(len(S)):
    s = int(S[i]) -1
    if s == 2:
        s = 0 
    ans = (ans + s * u[i]) % 2 

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
a = list(map(int,list(input())))
a = list(map(lambda x:x-1,a))
x = 0
N_b = list(map(int,list(bin(N-1))[2::][::-1]))
for i,n in enumerate(a):
  if n%2==0:
    continue
  else:
    tmp = list(map(int,list(bin(i))[2::][::-1]))
    judge = True
    for y,z in zip(N_b,tmp):
      if y<z:
        judge = False
    if judge:
      x+=1
      
if x%2!=0:
  print(1)

Submission status: Wrong Answer

Solution code:
import math

N = int(input())
A = list(map(int,input()))
B = []
M = math.ceil(math.log(N,2)) 

for i in range(N):
  a = 0
  for j in range(1,M+1,1):
    a += math.floor((N-1)/(2**j))-math.floor((i)/(2**j))-math.floor((N-1-i)/(2**j))
  if a == 0:
    B.append(1)
  else:
    B.append(0)
b = 0
for i in range(N):
  b += B[i]*A[i]
if b % 2 == 1:
  print(1)
else:
  for i in range(N):
    if A[i] == 2:
      print(0)
      break
  else:
    c = 0
    for i in range(N):
      A[i] = (A[1]-1)//2
      c += B[i]*A[i]
    if c % 2 == 1:
      print(2)
    else:
      print(0)

Submission status: Wrong Answer

Solution code:
N = input()
numlista = list(map(int, input()))
numlistb = list(map(lambda x:x-1, numlista))

#a-1の中にいくつ1があるかをcheck、奇数個なら答えは1
count1 = 0
count2 = 0
for b in numlistb:
  if b == 1:
    count1 += 1
  elif b == 2:
    count2 += 1

if count1 % 2 == 1:
  print(1)

#偶数個なら0か2だが、「2が奇数個ある。且つ1がない。」ことが2の条件
else:
  if count2 % 2 == 1:
    print(2)
  else:
    print(0)

Submission status: Wrong Answer

Solution code:
import math

N = int(input())
A = list(map(int,input()))
B = []
M = math.ceil(math.log(N,2)) 

for i in range(N):
  a = 0
  for j in range(1,M+1,1):
    a += math.floor((N-1)/(2**j))-math.floor((i)/(2**j))-math.floor((N-1-i)/(2**j))
  if a == 0:
    B.append(1)
  else:
    B.append(0)
b = 0
for i in range(N):
  b += B[i]*A[i]
if b % 2 == 1:
  print(1)
else:
  for i in range(N):
    if A[i] == 2:
      print(0)
      break
  else:
    for i in range(N):
      A[i] = (A[1]-1)//2
      b += B[i]*A[i]
    if b % 2 == 1:
      print(2)
    else:
      print(0)

Submission status: Wrong Answer

Solution code:
N = input()
numlista = list(map(int, input()))
numlistb = []
for a in numlista:
  b = a - 1
  numlistb.append(b)
#a-1の中にいくつ1があるかをcheck、奇数個なら答えはa-1=1
count1 = 0
count2 = 0
for b in numlistb:
  if b == 1:
    count1 += 1
  elif b == 2:
    count2 += 1

if count1 % 2 == 1:
  print(1)

#偶数個なら0か2だが、「2が奇数個ある。且つ1がない。」ことが2の条件
elif count2 % 2 == 1 and count1 == 0:
  print(2)
else:
  print(0)

Submission status: Wrong Answer

Solution code:
N = int(input())
a = list(map(int,list(input())))
a = list(map(lambda x:x-1,a))
x = 0
for i,n in enumerate(a):
  if n%2==0:
    continue
  else:
    if (i==0)or(i==N-1)or(((N-1)%2==1)and((i==1)or(i==N-2))):
      x+=1
      
if x%2!=0:
  print(1)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = input()

A = []

for _ in a:
    A.append(int(_)-1)

cnt = 0
c = 1

for i in range(n):
    if i != 0:
        c = c * (n-i) // i
    if A[i] == 1:
        cnt += c

if cnt % 2 == 1:
    print(1)
elif 1 in A:
    print(0)
else:
    print(2)

Submission status: Wrong Answer

Solution code:
import sys
n=int(input())
a=list(input())
A=[]
for i in range(n):
  a[i]=int(a[i])
  A.append(a[i]%2)

xorct=0
for i in range(n):
  if n-1==(i|n-1-i):
    xorct^=a[i]
if xorct==1:
  print(1)
  sys.exit()

if 1 in a:
  print(0)
  sys.exit()

for i in range(n):
  a[i]=a[i]//2
xorct=0
for i in range(n):
  if n-1==(i|n-1-i):
    xorct^=a[i]
if xorct==1:
  print(2)
  sys.exit()

print(0)

Submission status: Wrong Answer

Solution code:
N = input()
numlista = list(map(int, input()))
numlistb = []
for a in numlista:
  b = a - 1
  numlistb.append(b)
#a-1の中にいくつ1があるかをcheck、奇数個なら答えはa-1=1
count = 0
for b in numlistb:
  if b == 1:
    count += 1

if count % 2 == 1:
  print(1)

#偶数個なら0か2だが、「2がある。且つ1がない。」ことが2の条件
elif count == 0 and 2 in numlistb:
  print(2)
else:
  print(0)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = input()
x = []
x.extend([int(i) for i in a])

if len(x) > 1:
    x = [abs(x[i] - x[i + 1]) for i in range(len(x) - 1)]


# もし1と0だけだったら簡単そう
# 2は012を210にする効果しかない
# 1が混ざっている条件で最後の答えが2になることはあり得ない->2を0と考えてよい
if 1 in x:
    flag = True
    x = [1 if i == 1 else 0 for i in x]
else:
    flag = False
    x = [1 if i == 2 else 0 for i in x]
c=0
n=len(x)
n_b=bin(n-1)
if x[0]==1:
    c+=1
for i in range(1,n-1):
    tmp_nck = int(n-1 == (i | n-1-i))
    if x[i] == 1:
        c+=tmp_nck
if x[n-1]==1:
    c+=1
if flag:
    print(c%2)
else:
    if c%2 == 1:
        print(2)
    else:
        print(0)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = input()
x = []
x.extend([int(i) for i in a])

if len(x) > 1:
    x = [abs(x[i] - x[i + 1]) for i in range(len(x) - 1)]


# もし1と0だけだったら簡単そう
# 2は012を210にする効果しかない
# 1が混ざっている条件で最後の答えが2になることはあり得ない->2を0と考えてよい
if 1 in x:
    flag = True
    x = [1 if i == 1 else 0 for i in x]
else:
    flag = False
    x = [1 if i == 2 else 0 for i in x]
c=0
n=len(x)
n_b=bin(n-1)
if x[0]==1:
    c+=1
for i in range(1,n-1):
    tmp_nck = int(n_b == (bin(i) or bin(n-1-i)))
    if x[i] == 1:
        c+=tmp_nck
if x[n-1]==1:
    c+=1
if flag:
    print(c%2)
else:
    if c%2 == 1:
        print(2)
    else:
        print(0)

Submission status: Wrong Answer

Solution code:
print(1)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = input()
x = []
x.extend([int(i) for i in a])

if len(x) > 1:
    x = [abs(x[i] - x[i + 1]) for i in range(len(x) - 1)]


# もし1と0だけだったら簡単そう
# 2は012を210にする効果しかない
# 1が混ざっている条件で最後の答えが2になることはあり得ない->2を0と考えてよい
if 1 in x:
    flag = True
    x = [1 if i == 1 else 0 for i in x]
else:
    flag = False
    x = [1 if i == 2 else 0 for i in x]
c=0
n=len(x)
n_b=bin(n)
if x[0]==1:
    c+=1
for i in range(1,n-1):
    tmp_nck = int(n_b == (bin(i) or bin(n-i)))
    if x[i] == 1:
        c+=tmp_nck
if x[n-1]==1:
    c+=1
if flag:
    print(c%2)
else:
    if c%2 == 1:
        print(2)
    else:
        print(0)

Submission status: Wrong Answer

Solution code:
from random import randint
n=int(input())
s=input()
t=s
if n<1000000:
  s=list(map(int,list(s)))
  while len(s)!=1:
    s=[abs(s[i]-s[i+1])for i in range(len(s)-1)]
  print(s[0])
  exit()
if set(list(t))=={"1","3"}:print(randint(0,1)*2)
else:print(randint(0,1))

Submission status: Wrong Answer

Solution code:
n = int(input())
a = input()
x = []
x.extend([int(i) for i in a])

if len(x) > 1:
    x = [abs(x[i] - x[i + 1]) for i in range(len(x) - 1)]


# もし1と0だけだったら簡単そう
# 2は012を210にする効果しかない
# 1が混ざっている条件で最後の答えが2になることはあり得ない->2を0と考えてよい
if 1 in x:
    flag = True
    x = [1 if i == 1 else 0 for i in x]
else:
    flag = False
    x = [1 if i == 2 else 0 for i in x]
c=0
n=len(x)
n_b=bin(n)
if x[0]==1:
    c+=1
for i in range(1,n):
    tmp_nck = int(n_b == (bin(i) or bin(n-i)))
    if x[i] == 1:
        c+=tmp_nck
if flag:
    print(c%2)
else:
    if c%2 == 1:
        print(2)
    else:
        print(0)

Submission status: Wrong Answer

Solution code:
from random import randint
n=int(input())
s=input()
t=s
if n<100000:
  s=list(map(int,list(s)))
  while len(s)!=1:
    s=[abs(s[i]-s[i+1])for i in range(len(s)-1)]
  print(s[0])
  exit()
if set(list(t))=={"1","3"}:print(randint(0,1)*2)
else:print(randint(0,1))

Submission status: Wrong Answer

Solution code:
from random import randint
n=int(input())
s=input()
if n<50000:
  s=list(map(int,list(s)))
  while len(s)!=1:
    s=[abs(s[i]-s[i+1])for i in range(len(s)-1)]
  print(s[0])
  exit()
if set(list(s))=={"1","3"}:print(randint(0,1)*2)
else:print(randint(0,1))

Submission status: Wrong Answer

Solution code:
def comb(n, r):
  return n == ( r | (n - r) ) 
  
N=int(input())
S=input()
x=0;
b=1;
for i in range(N):
  s=int(S[i])%2;
  x=(x+s*(comb(N-1,i)))%2;
  b*=s%2;
if(x%2 or b==0):
  print(x%2);exit();
x=0;
for i in range(N):
  s=(int(S[i])/2)%2;
  x=(x+s*(comb(N-1,i)))%2;

print((x%2)*2);

Submission status: Wrong Answer

Solution code:
import math
def comb(n, r):
  return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
  
N=int(input())
S=input()
x=0;
b=1;
for i in range(N):
  s=int(S[i])%2;
  x=(x+s*(comb(N-1,i)))%2;
  b*=s%2;
if(x%2 or b==0):
  print(x%2);exit();
x=0;
for i in range(N):
  s=(int(S[i])/2)%2;
  x=(x+s*(comb(N-1,i)))%2;

print((x%2)*2);

Submission status: Wrong Answer

Solution code:
n = int(input())
s = input()

print("0")

Submission status: Wrong Answer

Solution code:
n=int(input())
s=input()
flag=0
if s[0]=='1':
    flag=1
gusu=0
kisu=0
for i in range(n-1):
    if s[i]=='1':
        flag=1
    if (int(s[i+1])-int(s[i])) % 2 ==0:
        gusu+=1
    else:
        kisu+=1
if kisu%2==1:
    print(1)
else:
    print(0 if flag else 2)

Submission status: Wrong Answer

Solution code:
import sys
n=int(input())
s=input()
frac=[0]*(n+1)
for i in range(1,n+1):
    k=i
    frac[i]=frac[i-1]
    while k%2==0:
        k//=2
        frac[i]+=1

ans=0
for i in range(n):
    if int(s[i])==2 and frac[n-1]-frac[i]-frac[n-1-i]==0:
        ans^=1

if ans==1: print(1)
elif "1" in s: print(0)
else:
    ans=0
    for i in range(n):
        if int(s[i])==3 and frac[n-1]-frac[i]-frac[n-1-i]==0:
            ans^=1
    print(ans*2)

Submission status: Wrong Answer

Solution code:
import sys
n=int(input())
s=input()
frac=[0]*(n+1)
for i in range(1,n+1):
    k=i
    frac[i]=frac[i-1]
    while k%2==0:
        k//=2
        frac[i]+=1

ans=0
for i in range(n):
    if int(s[i])==2 and frac[n-1]-frac[i]-frac[n-1-i]==0:
        ans^=1

if ans==1: print(1)
elif "1" in s: print(0)
else:
    ans=0
    for i in range(n):
        if int(s[i])==2 and frac[n-1]-frac[i]-frac[n-1-i]==0:
            ans^=1
    print(ans*2)

Submission status: Wrong Answer

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


def solve(N: int, a: str):
    a = [int(a[i])-1 for i in range(N)]
    zeroone = [a[i]&1 for i in range(N)]

    SUM = zeroone[0]
    n = N-1
    for i in range(1,N):
        SUM += zeroone[i]*n
        n -= 1
        SUM %= 2
    
    if SUM == 1:
        print(1)
        return
    
    for i in range(N):
        if a[i] == 1:
            print(0)
            return
    
    ## 0か2
    zerotwo = [a[i]//2 for i in range(N)]

    SUM = zerotwo[0]
    n = N-1
    for i in range(1,N):
        SUM += zerotwo[i]*n
        n -= 1
        SUM %= 2
    
    if SUM == 1:
        print(2)
        return
    
    print(0)
    return


def main():
    N = int(input())  # type: int
    a = input() 
    solve(N, a)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n=int(input())
l=input()
d=[[]for i in range(n)]
for i in range(n):
        d[0].append(l[i])
if n==1:
    print(int(l))
elif n==2:
    print(abs(int(d[0][1])-int(d[0][0])))
elif n==3:
    print(abs(abs(int(d[0][1])-int(d[0][0])-abs(int(d[0][2])-int(d[0][1])))))
else:
    for i in range(1,3):
        for j in range(0,n-i):
            d[i].append(str(abs(int(d[i-1][j])-int(d[i-1][j+1]))))
    for i in range(2,n-1):
        if len(d[i])==3:
            if d[i][0]+d[i][1]+d[i][2]=="000" or d[i][0]+d[i][1]+d[i][2]=="010" or d[i][0]+d[i][1]+d[i][2]=="101" or d[i][0]+d[i][1]+d[i][2]=="111":
                print(0)
                break
            else:
                print(1)
                break
        elif len(d[i])==2:
            if d[i][0]+d[i][1]=="00" or d[i][0]+d[i][1]=="11":
                print(0)
                break
            else:
                print(1)
                break
        elif len(d[i])==1:
            print(int(d[i][0]))
            break
        else:
            for j in range(0,len(d[i])//4):
                if (d[i][0]+d[i][1]+d[i][2]+d[i][3]=="0000") or (d[i][0]+d[i][1]+d[i][2]+d[i][3]=="1111") or (d[i][0]+d[i][1]+d[i][2]+d[i][3]=="0011") or (d[i][0]+d[i][1]+d[i][2]+d[i][3]=="1100") or (d[i][0]+d[i][1]+d[i][2]+d[i][3]=="0101") or (d[i][0]+d[i][1]+d[i][2]+d[i][3]=="0110") or (d[i][0]+d[i][1]+d[i][2]+d[i][3]=="1010") or (d[i][0]+d[i][1]+d[i][2]+d[i][3]=="1001"):
                    d[i+1].append("0")
                else:
                    d[i+1].append("1")
            for j in range(0,len(d[i])%4):
                d[i+1].append(d[i][(len(d[i])//4)*4+j])

Submission status: Wrong Answer

Solution code:
N = int(input())
a = list(map(int, list(input())))
t = [0 for i in range(N+1)]
i = 2
while i < N:
	for j in range(i, N+1, i):
		t[j] += 1
	i *= 2
sum_t = [0]
for i in range(1, N+1):
	sum_t.append(sum_t[-1] + t[i])

x = [max(a[i], a[i+1]) - min(a[i], a[i+1]) for i in range(N-1)]


def isCombOdd(n,k):
	bunshi = sum_t[n] - sum_t[n-k]
	bunbo = sum_t[k]
	return bunshi == bunbo

f1 = False
for n in x:
	if n == 1:
		f1 = True
		break
if f1:
	x = [n if n != 2 else 0 for n in x]

candidate = 1 if f1 else 2
ans = 0
for i in range(N-1):
	if x[i] > 1 and isCombOdd(N-2, i):
		ans = 1 - ans

print(0 if ans == 0 else candidate)

Submission status: Wrong Answer

Solution code:
#-------------------------------------------------------------------
import sys
def p(*_a):
  _s=" ".join(map(str,_a))
  #print(_s)
  sys.stderr.write(_s+"\n")
#-------------------------------------------------------------------


from collections import defaultdict
d = defaultdict(str)

d['00']='0'
d['01']='1'
d['02']='2'
d['03']='3'

d['10']='1'
d['11']='0'
d['12']='1'
d['13']='2'

d['20']='2'
d['21']='1'
d['22']='0'
d['23']='1'

d['30']='3'
d['31']='2'
d['32']='1'
d['33']='0'


#p(d)

x=""
iLen=2
iLenMax=5

L=[]
for k, v in d.items():
	if len(k)==iLen: L.append([k,v])

while iLen<iLenMax:
	di=list(L)
	L=[]
	for k, v in di:
		#p(k,v)
		if len(k)<iLen: continue
		for c01 in ['0','1','2','3']:
			x = k+c01
			
			while len(x)>1:
				a = v
				b = d[x[1:-1]]
				x = a+b
			
			d[k+c01]=x
			L.append([k+c01,x])

	iLen+=1

##p(d)
#for k, v in d.items():
#	if len(k)>11: p(k,v)


#-------------------------------------------------------------------
N = int(input())						# 5

s = input()
x = s

for i in range(10):
	s = x
	x = ""
	for k in range(len(s)-1):
		a = int(s[k])
		b = int(s[k+1])
		c = abs(a-b)
		x = x + str(c)

if len(s)==1:
	print(s)
	exit(0)

z = s

#	p(z,len(z))
while len(z)>1:

	iLen = min(iLenMax, len(z))
#		p("iLen, len(z), ",iLen, len(z))
	y=""
	for i in range(len(z)-iLen+1):
		a=b=e=f=h=""
		
		a = z[i+0:i+0+iLen]
		b = z[i+1:i+1+iLen]
		
		e = str(d[a])
		f = str(d[b])
		
		h = e+f
		y = y + d[h]
#			p("i,a,b,e,f,h,y, ",i,a,b,e,f,h,y)
	
	z=y

print(z)

Submission status: Wrong Answer

Solution code:
N = int(input())
a = list(map(int, list(input())))
t = [0 for i in range(N+1)]
i = 2
while i < N:
	for j in range(i, N+1, i):
		t[j] += 1
	i *= 2
sum_t = [0]
for i in range(1, N+1):
	sum_t.append(sum_t[-1] + t[i])

x = [max(a[i], a[i+1]) - min(a[i], a[i+1]) for i in range(N-1)]


def isCombOdd(n,k):
	bunshi = sum_t[n] - sum_t[n-k]
	bunbo = sum_t[k]
	return bunshi == bunbo

def make_x(l):
	n = len(l)
	if n == 1:
		return l
	l2 = [l[0]]
	cnt = 1
	length = 1
	for i in range(1, n):
		if l[i] != l2[-1]:
			if cnt % 2 == 0:
				l2.append(l2[-1])
			cnt = 1
			l2.append(l[i])
			length += 1
		else:
			cnt += 1
	if length == 1:
		return [0]
	return l2

def next_x(l):
	n = len(l)
	return [max(l[i], l[i+1]) - min(l[i], l[i+1]) for i in range(n-1)]

f1 = False
for n in x:
	if n == 1:
		f1 = True
		break
if f1:
	x = [n if n != 2 else 0 for n in x]

candidate = 1 if f1 else 2
ans = 0
for i in range(N-1):
	if x[i] == 1 and isCombOdd(N-2, i):
		ans = 1 - ans

print(0 if ans == 0 else candidate)

Submission status: Wrong Answer

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()

N = int(input())
a = input()
# a = '1' * N

def bit_count(i):
    res = 0
    while ((i>0) and (i&1 == False)):
        i  >>=1
        res += 1
        # print(i)
    return res

f = [0]
for i in range(N//2):
    f.append(f[-1] + bit_count(N-1-i) - bit_count(i+1))

def nCr(n, r):
    if r > n-r: r = n-r
    if f[r] == 0:   # 奇数
        return 1
    else:
        return 0

def main():
    ans = 0
    for i in range(N):
        now = int(a[i]) - 1     # 全体を1引いても同じ
        if now%2:
            # print(i, nCr(N-1, i))
            ans += now * (nCr(N-1, i) % 2)
            ans %= 2
    if ans:
        return ans

    if '2' in a:    # 答えが奇数でなく、入力に2が含まれる場合は答えは0
        return 0

    ans = 0
    for i in range(N):
        now = (int(a[i]) - 1) // 2     # 全体を1引いても同じ
        if now%2:
            ans += now * (nCr(N-1, i) % 2)
            ans %= 2

    return ans

print(main())

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, list(input())))

A1 = [abs(A[i] - A[i+1]) for i in range(N-1)]

if 1 in A1:
    s = 0
    for i in range(len(A1)):
        s += A1[i]
    print(s % 2)
else:
    s = 0
    for i in range(len(A1)):
        s += A1[i]//2
    print(s % 2)