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:

n=int(input())
a=list(map(lambda x:int(x)-1,list(input())))
def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 2 #出力の制限
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, n + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )


def slv(n,a):
    # 答えの偶奇を求める
    chk=0
    for i in range(n):
        x=a[i]%2
        chk+=a[i]*cmb(n-1,i+1,2)
        chk%=2
    if chk:return 1
    if 1 in a:return 0
    return 2

#n=pow(10,5)
#a=[i%3 for i in range(n)]
print(slv(n,a))
exit()
x=[[0]*n for _ in range(n)]
for i in range(n):
    x[0][i]=a[i]
for i in range(1,n):
    for j in range(n-i):
        x[i][j]=abs(x[i-1][j]-x[i-1][j+1])
for i,xx in enumerate(x):
    print(xx[:n-i])

Submission status: Wrong Answer

Solution code:
def slv(n,a):
    # 答えの偶奇を求める
    chk=0
    tmp=1
    for i in range(n):
        x=a[i]%2
        chk+=a[i]*tmp
        chk%=2
        tmp*=n-i-1
        tmp*=pow(i+1,2-2,2)
        tmp%=2
    if chk:return 1
    if 1 in a:return 0
    return 2

n=int(input())
a=list(map(lambda x:int(x)-1,list(input())))
#n=pow(10,5)
#a=[i%3 for i in range(n)]
print(slv(n,a))
"""
x=[[0]*n for _ in range(n)]
for i in range(n):
    x[0][i]=a[i]
for i in range(1,n):
    for j in range(n-i):
        x[i][j]=abs(x[i-1][j]-x[i-1][j+1])
for i,xx in enumerate(x):
    print(xx[:n-i])
"""

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

def main():
    n = int(input())
    s = input()
    sub = [int(s[i])-1 for i in range(n)]
    
    table = [0]*(n+1)
    p = 2
    for i in range(len(bin(n))-1):
        for j in range(p, n+1, p):
            table[j] += 1
        p *= 2
    
    for i in range(n):
        table[i+1] += table[i]
    
    ans = 0
    for i in range(n):
        if sub[i]%2:
            judge = table[n-1]-table[n-1-i]-table[i]
            if not judge:
                ans += 1
    
    
    if ans%2:
        print(1)
    else:
        if 1 in sub:
            print(0)
        else:
            j1, j2 = False, False
            for i in range(n-1):
                if sub[i]-sub[i+1] == 0:
                    j1 = True
                else:
                    j2 = True
            print((j1+j2-1)*2)
    
        
    
    
    
    
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
import math
import heapq
mod=10**9+7
inf=float("inf")
from math import sqrt, ceil
from collections import deque, Counter, defaultdict, OrderedDict
#すべてのkeyが用意されてる defaultdict(int)で初期化
#順序を保ったdict
input=lambda: sys.stdin.readline().strip()
sys.setrecursionlimit(11451419)
from decimal import ROUND_HALF_UP,Decimal  #変換後の末尾桁を0や0.01で指定
  #Decimal((str(0.5)).quantize(Decimal('0'), rounding=ROUND_HALF_UP))
from functools import lru_cache
#メモ化再帰defの冒頭に毎回 @lru_cache(maxsize=10**10)
#引数にlistはだめ
#######ここまでテンプレ#######
#ソート、"a"+"b"、再帰ならPython3の方がいい
#######ここから天ぷら########
n=int(input())
s=input()
A=[int(i)-1 for i in s]

RUI2=[pow(2,i) for i in range(21)]
import bisect as bi
@lru_cache(maxsize=10**10)
def tan(n):
    if n==0:return [1]
    if n==1:return [1,1]
    if n==2:return [1,0,1]
    i= bi.bisect_right(RUI2,n)-1
    return tan(n-pow(2,i)) + [0]*(pow(2,i+1)-n-1) + tan(n-pow(2,i))


# for i in range(n-1):
#     if A[i]==A[i+1]: A[i]=0
#     elif (A[i]^A[i+1])&1 : A[i]=1
#     else:A[i]=2
# for i in range(n-2):
#     if (A[i]^A[i+1])&1 : A[i]=1
#     else:A[i]=0

# print(A[:-2],tan(n-3))
if A.count(1)!=0:
    A=[i%2!=1 for i in A]
    a=[i&j for i,j in zip(A,tan(n-1))]
    # print(a)
    print(1 if sum(a)%2==1 else 0)
else:
    a=[(i-1)&j for i,j in zip(A,tan(n-1))]
    print(2 if sum(a)%2==1 else 0)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
a = list(map(int, list(input())[: -1]))
combi = [[0, 0], [1, 1]]
bnN = list(bin(N - 1))[2: ]
res = 0
rres = 0
for i in range(N):
  bni = list(bin(i))[2: ]
  bni = (len(bnN) - len(bni)) * [0] + bni
  t = 1
  for x in range(len(bnN)): t *= combi[int(bnN[x])][int(bni[x])]
  res ^= t * a[i] % 2
  a[i] //= 2
  for x in range(len(bnN)): t *= combi[int(bnN[x])][int(bni[x])]
  rres ^= t * a[i] % 2
if (2 in a) and res == 0: print(0)
elif res == 1: print(1)
else:
  if rres: print(2)
  else: print(0)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
a = list(map(int, list(input())[: -1]))

combi = [[0, 0], [1, 1]]
bnN = list(bin(N - 1))[2: ]
res = 0
for i in range(N):
  bni = list(bin(i))[2: ]
  bni = (len(bnN) - len(bni)) * [0] + bni
  t = 1
  for x in range(len(bnN)): t *= combi[int(bnN[x])][int(bni[x])]
  res ^= t * a[i] % 2
if not (2 in a) and res == 0: print(2)
else: print(res)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
a = list(map(int, list(input())[: -1]))

class Factorial:
  def __init__(self, n, mod):
    self.mod = mod
    self.f = [1]
    for i in range(1, n + 1):
      self.f.append(self.f[-1] * i % mod)
    self.i = [pow(self.f[-1], mod - 2, mod)]
    for i in range(1, n + 1)[: : -1]:
      self.i.append(self.i[-1] * i % mod)
    self.i.reverse()
  def factorial(self, i):
    return self.f[i]
  def ifactorial(self, i):
    return self.i[i]
  def combi(self, n, k):
    return self.f[n] * self.i[n - k] % self.mod * self.i[k] % self.mod
  def permi(self, n, k):
    return self.f[n] * self.i[n - k] % self.mod
f = Factorial(N, 10 ** 9 + 7)
res = 0
for i in range(N):
  res ^= f.combi(N - 1, i) * (a[i] - 1) % 2
if not (2 in a) and res == 0: print(2)
else: print(res)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
a = list(map(int, list(input())[: -1]))
if a.count(3) == N - 1:
  if a[0] == 1 or (a[-1] == 1):
    print(2)
    exit(0)
if a.count(1) == N - 1:
  if a[0] == 3 or (a[-1] == 3):
    print(2)
    exit(0)
class Factorial:
  def __init__(self, n, mod):
    self.mod = mod
    self.f = [1]
    for i in range(1, n + 1):
      self.f.append(self.f[-1] * i % mod)
    self.i = [pow(self.f[-1], mod - 2, mod)]
    for i in range(1, n + 1)[: : -1]:
      self.i.append(self.i[-1] * i % mod)
    self.i.reverse()
  def factorial(self, i):
    return self.f[i]
  def ifactorial(self, i):
    return self.i[i]
  def combi(self, n, k):
    return self.f[n] * self.i[n - k] % self.mod * self.i[k] % self.mod
  def permi(self, n, k):
    return self.f[n] * self.i[n - k] % self.mod
f = Factorial(N, 10 ** 9 + 7)
res = 0
for i in range(N):
  res ^= f.combi(N - 1, i) * a[i] % 2
if not (2 in a) and res == 0: print(2)
else: print(res)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
a = list(map(int, list(input())[: -1]))
if a.count(3) == N - 1:
  if a[0] == 1 or (a[-1] == 1):
    print(2)
    exit(0)
if a.count(1) == N - 1:
  if a[0] == 3 or (a[-1] == 3):
    print(2)
    exit(0)
class Factorial:
  def __init__(self, n, mod):
    self.mod = mod
    self.f = [1]
    for i in range(1, n + 1):
      self.f.append(self.f[-1] * i % mod)
    self.i = [pow(self.f[-1], mod - 2, mod)]
    for i in range(1, n + 1)[: : -1]:
      self.i.append(self.i[-1] * i % mod)
    self.i.reverse()
  def factorial(self, i):
    return self.f[i]
  def ifactorial(self, i):
    return self.i[i]
  def combi(self, n, k):
    return self.f[n] * self.i[n - k] % self.mod * self.i[k] % self.mod
  def permi(self, n, k):
    return self.f[n] * self.i[n - k] % self.mod
f = Factorial(N, 10 ** 9 + 7)
res = 0
for i in range(N):
  res ^= f.combi(N - 1, i) * (a[i] - 1) % 2
print(res)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
a = list(map(int, list(input())[: -1]))
if a.count(3) == N - 1:
  if a[0] == 1 or (a[-1] == 1):
    print(2)
    exit(0)
if a.count(1) == N - 1:
  if a[0] == 3 or (a[-1] == 3):
    print(2)
    exit(0)
class Factorial:
  def __init__(self, n, mod):
    self.mod = mod
    self.f = [1]
    for i in range(1, n + 1):
      self.f.append(self.f[-1] * i % mod)
    self.i = [pow(self.f[-1], mod - 2, mod)]
    for i in range(1, n + 1)[: : -1]:
      self.i.append(self.i[-1] * i % mod)
    self.i.reverse()
  def factorial(self, i):
    return self.f[i]
  def ifactorial(self, i):
    return self.i[i]
  def combi(self, n, k):
    return self.f[n] * self.i[n - k] % self.mod * self.i[k] % self.mod
  def permi(self, n, k):
    return self.f[n] * self.i[n - k] % self.mod
f = Factorial(N, 10 ** 9 + 7)
res = 0
for i in range(N):
  res ^= f.combi(N - 1, i) * a[i] % 2
print(res)

Submission status: Wrong Answer

Solution code:
from scipy.special import comb
n = int(input())
l = list(input())
a = []
for i in l:
    a.append(int(i))
ans = 0
for i in range(1, n + 1):
    if (n - 1 & i) % 2 == 1:
        ans ^= int(a[i-1])
if ans % 2 == 0:
    print(1)
else:
    if "2" in l:
        print(0)
    else:
        print(2)

Submission status: Wrong Answer

Solution code:
from scipy.special import comb
n = int(input())
l = list(input())
a = []
for i in l:
    a.append(int(i))
print(a)
ans = 0
for i in range(1, n + 1):
    if (n - 1 & i) % 2 == 1:
        ans ^= int(a[i-1])
if ans % 2 == 0:
    print(1)
else:
    if "2" in l:
        print(0)
    else:
        print(2)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

N = int(input())
a = list(map(int, list(input()[:-1])))
a = list(map(lambda x: x-1, a))
p = [0]*N

for i in range(1, N):
    t = i
    
    while t%2==0:
        t //= 2
        p[i] += 1

for i in range(1, N):
    p[i] += p[i-1]

X = 0

for i in range(N):
    if a[i]==1 and p[N-1-i]+p[i]==p[N-1]:
        X += 1

if X%2==1:
    print(1)
else:
    if 1 in a:
        print(0)
    else:
        print(2*(X%2))

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gcd, sqrt
from operator import mul
from functools import reduce
from operator import mul
from pprint import pprint
from copy import deepcopy



sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 2


n = I()
s = S()
l = len(s)
L = []
one_cnt = 0
for i in range(l - 1):
    ret = abs(int(s[i]) - int(s[i + 1]))
    L += [ret]
    if ret == 1:
        one_cnt += 1

m = 0
for j in range(l - 1):
    if min(j, l - 2 - j) == 0 or ((l - 2) % 2 and min(j, l - 2 - j) == 1):
        mm = 1
    else:
        mm = 0
    m += mm * L[j]
    m %= 2

if m % 2:
    print(1)
    exit()
else:
    if one_cnt:
        print(0)
    else:
        L = [k // 2 for k in L]
        ret2 = 0
        for jj in range(l - 1):
            if min(jj, l - 2 - jj) == 0 or ((l - 2) % 2 and min(jj, l - 2 - jj) == 1):
                mm = 1
            else:
                mm = 0
            ret2 += mm * L[jj]
            ret2 %= 2
        if ret2:
            print(2)
        else:
            print(0)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gcd, sqrt
from operator import mul
from functools import reduce
from operator import mul
from pprint import pprint
from copy import deepcopy



sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 2


n = I()
s = S()
l = len(s)
L = []
one_cnt = 0
for i in range(l - 1):
    ret = abs(int(s[i]) - int(s[i + 1]))
    L += [ret]
    if ret == 1:
        one_cnt += 1

m = 0
for j in range(l - 1):
    if min(j, l - 2 - j) == 0 or ((l - 2) % 2 and min(j, l - 2 - j) == 1):
        mm = 1
    else:
        mm = 0
    m += mm * L[j]
    m %= 2

if m % 2:
    print(1)
    exit()
else:
    if one_cnt:
        print(0)
    else:
        L = [k // 2 for k in L]
        ret2 = 0
        for jj in range(l - 1):
            if min(jj, l - 2 - j) == 0 or ((l - 2) % 2 and min(jj, l - 2 - j) == 1):
                mm = 1
            else:
                mm = 0
            ret2 += mm * L[jj]
            ret2 %= 2
        if ret2:
            print(2)
        else:
            print(0)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gcd, sqrt
from operator import mul
from functools import reduce
from operator import mul
from pprint import pprint
from copy import deepcopy



sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n = I()
fac = [1] * (n + 1)
inv = [1] * (n + 1)
for j in range(1, n + 1):
    fac[j] = fac[j-1] * j % mod


inv[n] = pow(fac[n], mod-2, mod)
for j in range(n-1, -1, -1):
    inv[j] = inv[j+1] * (j+1) % mod


def comb(n, r):
    if r > n or n < 0 or r < 0:
        return 0
    return fac[n] * inv[n - r] * inv[r] % mod



s = S()
l = len(s)
L = []
one_cnt = 0
for i in range(l - 1):
    ret = abs(int(s[i]) - int(s[i + 1]))
    L += [ret]
    if ret == 1:
        one_cnt += 1

m = 0
for j in range(l - 1):
    m += comb(l - 2, min(j, l - 2 - j)) * L[j]
    m %= 2

if m % 2:
    print(1)
    exit()
else:
    if one_cnt:
        print(0)
        exit()
    else:
        L = [k // 2 for k in L]
        ret2 = 0
        for jj in range(l - 1):
            ret2 += comb(l - 2, min(jj, l - 2 - jj)) * L[jj]
            ret2 %= 2
        if ret2:
            print(2)
        else:
            print(0)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gcd, sqrt
from operator import mul
from functools import reduce
from operator import mul
from pprint import pprint
from copy import deepcopy



sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n = I()
fac = [1] * (n + 1)
inv = [1] * (n + 1)
for j in range(1, n + 1):
    fac[j] = fac[j-1] * j % mod


inv[n] = pow(fac[n], mod-2, mod)
for j in range(n-1, -1, -1):
    inv[j] = inv[j+1] * (j+1) % mod


def comb(n, r):
    if r > n or n < 0 or r < 0:
        return 0
    return fac[n] * inv[n - r] * inv[r] % mod



s = S()
l = len(s)
L = []
one_cnt = 0
for i in range(l - 1):
    ret = abs(int(s[i]) - int(s[i - 1]))
    L += [ret]
    if ret == 1:
        one_cnt += 1

ret = 0
for j in range(l - 1):
    ret += comb(l - 2, j) * L[j]
    ret %= 2

if ret % 2:
    print(1)
    exit()
else:
    if one_cnt:
        print(0)
        exit()
    else:
        L = [k // 2 for k in L]
        ret2 = 0
        for j in range(l - 1):
            ret2 += comb(l - 2, j) * L[j]
            ret2 %= 2
        if ret2:
            print(2)
        else:
            print(1)

Submission status: Wrong Answer

Solution code:
n = int(input())
L = list(input())
L = [int(x) for x in L]

while len(L) >1:
    for i in range(len(L)-1):
        L[i] = abs(L[i+1]-L[i])
    L.pop()
    if all([x<=1 for x in L]):
        break
if sum(L)%2  ==1:
    print(1)
else:
    print(0)

Submission status: Wrong Answer

Solution code:
N=int(input())
A=[0]*(N+1)
A[2]==1
for i in range(1,N+1):
 if i%2==0:
  A[i]=A[i//2]+1 
B=[0]*(N+1)
for i in range(1,N+1):
 B[i]=B[i-1]+A[i]
a=[int(d) for d in input()]
if a[0]==1 and a[N-1]==3:
 ans=0
 b=1
 c=0
 for i in range(N):
  if a[i]==1 or a[i]==3:
   if B[N-1]-B[i]-B[N-1-i]==0: 
    ans+=1
   if a[i]!=b:
    c+=1
    b=3
  else:
   c+=1
 if c==1:
  print(2)
 else:
  print(ans%2)
elif a[0]==3 and a[N-1]==1:
 ans=0
 b=3
 c=0
 for i in range(N):
  if a[i]==1 or a[i]==3:
   if B[N-1]-B[i]-B[N-1-i]==0: 
    ans+=1
   if a[i]!=b:
    c+=1
    b=1
  else:
   c+=1
 if c==1:
  print(2)
 else:
  print(ans%2)
else:
 ans=0
 for i in range(N):
  if a[i]==1 or a[i]==3:
   if B[N-1]-B[i]-B[N-1-i]==0: 
    ans+=1
 print(ans%2)

Submission status: Wrong Answer

Solution code:
N=int(input())
A=[0]*(N+1)
A[2]==1
for i in range(1,N+1):
 if i%2==0:
  A[i]=A[i//2]+1 
B=[0]*(N+1)
for i in range(1,N+1):
 B[i]=B[i-1]+A[i]
a=[int(d) for d in input()]
if a[0]==1 and a[N-1]==3:
 ans=0
 b=1
 c=0
 for i in range(N):
  if a[i]==1 or a[i]==3:
   if B[N]-B[i]-B[N-i]==0: 
    ans+=1
   if a[i]!=b:
    c+=1
    b=3
  else:
   c+=1
 if c==1:
  print(2)
 else:
  print(ans%2)
elif a[0]==3 and a[N-1]==1:
 ans=0
 b=3
 c=0
 for i in range(N):
  if a[i]==1 or a[i]==3:
   if B[N]-B[i]-B[N-i]==0: 
    ans+=1
   if a[i]!=b:
    c+=1
    b=1
  else:
   c+=1
 if c==1:
  print(2)
 else:
  print(ans%2)
else:
 ans=0
 for i in range(N):
  if a[i]==1 or a[i]==3:
   if B[N-1]-B[i]-B[N-1-i]==0: 
    ans+=1
 print(ans%2)

Submission status: Wrong Answer

Solution code:
N=int(input())
A=[0]*(N+1)
A[2]==1
for i in range(1,N+1):
 if i%2==0:
  A[i]=A[i//2]+1 
B=[0]*(N+1)
for i in range(1,N+1):
 B[i]=B[i-1]+A[i]
a=[int(d) for d in input()]
if a[0]==1 and a[N-1]==3:
 ans=0
 b=1
 c=0
 for i in range(N):
  if a[i]==1 or a[i]==3:
   if B[N-1]-B[i]-B[N-1-i]==0: 
    ans+=1
   if a[i]!=b:
    c+=1
    b=3
  else:
   c+=1
 if c==1:
  print(2)
 else:
  print(ans%2)
elif a[0]==3 and a[N-1]==1:
 ans=0
 b=3
 c=0
 for i in range(N):
  if a[i]==1 or a[i]==3:
   if B[N-1]-B[i]-B[N-1-i]==0: 
    ans+=1
   if a[i]!=b:
    c+=1
    b=1
  else:
   c+=1
 if c==1:
  print(2)
 else:
  print(ans%2)
else:
 ans=0
 for i in range(N):
  if a[i]==1 or a[i]==3:
   if B[N-1]-B[i]-B[N-1-i]==0: 
    ans+=1
 print(ans%2)
print(B)

Submission status: Wrong Answer

Solution code:
N=int(input())
A=[0]*(N+1)
A[2]==1
for i in range(1,N+1):
 if i%2==0:
  A[i]=A[i//2]+1 
B=[0]*(N+1)
for i in range(1,N+1):
 B[i]=B[i-1]+A[i]
a=[int(d) for d in input()]
if a[0]==1 and a[N-1]==3:
 ans=0
 b=1
 c=0
 for i in range(N):
  if a[i]==1 or a[i]==3:
   if B[N]-B[i]-B[N-i]==0: 
    ans+=1
   if a[i]!=b:
    c+=1
    b=3
  else:
   c+=1
 if c==1:
  print(2)
 else:
  print(ans%2)
elif a[0]==3 and a[N-1]==1:
 ans=0
 b=3
 c=0
 for i in range(N):
  if a[i]==1 or a[i]==3:
   if B[N]-B[i]-B[N-i]==0: 
    ans+=1
   if a[i]!=b:
    c+=1
    b=1
  else:
   c+=1
 if c==1:
  print(2)
 else:
  print(ans%2)
else:
 ans=0
 for i in range(N):
  if a[i]==1 or a[i]==3:
   if B[N]-B[i]-B[N-i]==0: 
    ans+=1
 print(ans%2)

Submission status: Wrong Answer

Solution code:
def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 2 #出力の制限
N = 10**6+1
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

N=int(input())
a=[int(d) for d in input()]
if a[0]==1 and a[N-1]==3:
 ans=0
 b=1
 c=0
 for i in range(N):
  if a[i]==1 or a[i]==3:
   ans+=cmb(N-1, i,2)
   if a[i]!=b:
    c+=1
    b=3
 if c==1:
  print(2)
 else:
  print(ans%2)
elif a[0]==3 and a[N-1]==1:
 ans=0
 b=3
 c=0
 for i in range(N):
  if a[i]==1 or a[i]==3:
   ans+=cmb(N-1, i,2)
   if a[i]!=b:
    c+=1
    b=1
 if c==1:
  print(2)
 else:
  print(ans%2)
else:
 ans=0
 for i in range(N):
  if a[i]==1 or a[i]==3:
   ans+=cmb(N-1, i,2)
 print(ans%2)

Submission status: Wrong Answer

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

S1 = []
for i in range(N-1):
    now = abs(int(S[i+1])-int(S[i]))
    if now != 0:
        S1.append(now)

cnt = 0
for i in range(len(S1)):
    if S[i] != S[i+1]:
        cnt += 1

print(cnt % 2)

Submission status: Wrong Answer

Solution code:

import sys
input = sys.stdin.readline
N = int(input())
A = list(input().rstrip())

def two_num(x):
    res = 0
    while x%2==0:
        x //= 2
        res += 1
    return res

C_twos = [0]*N
for i in range(1, N):
    res = C_twos[i-1] + two_num(N-i) - two_num(i)
    C_twos[i] = res

if '1' in A:
    ans = 0
    for i in range(N):
        ans ^= int(A[i])&1 * (C_twos[i]==0)
    print(ans)
else:
    ans = 0
    for i in range(N):
        ans ^= int(A[i])&2 * (C_twos[i]==0)
    print(ans*2)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = [int(x) for x in input()]
for i in range(n):
    a[i] -= 1

f = False

if not(1 in a):
    f = True
    for i in range(n):
        a[i] //= 2


ans = 0

for i in range(n):
    if a[i] == 1:
        ans += not(((i+1) ^ n) == 0)

ans %= 2

if f:
    ans *= 2

print(ans)

Submission status: Wrong Answer

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

b = [abs(a[i] - a[i + 1]) for i in range(n - 1)]

if n > 2:
    ans = abs(b[0] - b[-1])
else:
    ans = b[0]
print(ans)

Submission status: Wrong Answer

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

x = [[0 for i in range(n+1)] for j in range(n+1)]

for i, a_i in enumerate(a):
	x[1][i+1] = a_i

for i in range(2, n+1):
	for j in range(1, n+2-i):
		x[i][j] = abs(x[i-1][j] - x[i-1][j+1])
print(x)
print(x[n][1])

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6) #再帰関数の上限
import math
from copy import copy, deepcopy
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque 
#deque(l), pop(), append(x), popleft(), appendleft(x)
##listでqueの代用をするとO(N)の計算量がかかってしまうので注意
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
#import fractions#古いatcoderコンテストの場合GCDなどはここからimportする


def input(): return sys.stdin.readline()[:-1]
def printl(li): print(*li, sep="\n")
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)

def main():
    mod = 10**9+7
    #w.sort(key=itemgetter(1),reversed=True)  #二個目の要素で降順並び替え

    N = int(input())
    #N, K = map(int, input().split())
    a=input() #1行ベクトル
    A=[int(a[i]) for i in range(N)]
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列

    while True:
        l=[]
        for i in range(len(A)-1):
            x=abs(A[i]-A[i+1])
            if x>0:
                l.append(x)
        if len(l)<2:
            break
        A=copy(l)
    if len(l)==0:
        return 0
    return l[0]






if __name__ == "__main__":
    print(main())

Submission status: Wrong Answer

Solution code:
#dpでできないかな？
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,cos,radians,sqrt
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

n=I()
s=list(map(int,SI()))
if n==1:
    print(s[0])
    sys.exit()

def divi2(x):
    if x%2==1:
        return 0
    else:
        count=0
        while x%2==0:
            x//=2
            count+=1
        return count
#print(divi2(24))
pw2=[0 for i in range(n-1)]
for i in range(n-1):
    if i%2==1:
        pw2[i]=divi2(i+1)
#print(pw2)
#print(s)
cmbnk2=[0 for i in range(n)]
for i in range(n-1):
    cmbnk2[i+1]=cmbnk2[i]+pw2[n-2-i]-pw2[i]
#print(cmbnk2)
ans=0
if (s.count(1)==1 and not 2 in s ) or (s.count(3)==1 and not 2 in s ):
    ans=2
    print(ans)
    sys.exit()
else:
    for i in range(n):
        if cmbnk2[i]==0:
            ans+=s[i]%2
            #print(s[i]%2)
        #print(cmbnk2[i]%2+1)
        #print(s[i])
print(ans%2)

Submission status: Wrong Answer

Solution code:
#dpでできないかな？
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,cos,radians,sqrt
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

n=I()
s=list(map(int,SI()))
if n==1:
    print(s[0])
    sys.exit()

def divi2(x):
    if x%2==1:
        return 0
    else:
        count=0
        while x%2==0:
            x//=2
            count+=1
        return count
#print(divi2(24))
pw2=[0 for i in range(n-1)]
for i in range(n-1):
    if i%2==1:
        pw2[i]=divi2(i+1)
#print(pw2)
cmbnk2=[0 for i in range(n)]
for i in range(n-1):
    cmbnk2[i+1]=cmbnk2[i]+pw2[n-2-i]-pw2[i]
#print(cmbnk2)
#u=[1 for i in range(n-1)]+[3]
ans=0
#print(s)
#print(u)
if (s.count(1)==1 and not 2 in s ) or (s.count(3)==1 and not 2 in s ):
    ans=2
    print(ans)
    sys.exit()
else:
    for i in range(n):
        if cmbnk2[i]==0:
            ans+=s[i]
        #print(cmbnk2[i]%2+1)
        #print(s[i])
print(ans%2)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    N=int(input())
    a=list(map(int1,input()))
    X=0
    c=0
    f=False
    if not 1 in a:
        for i in range(N):
            a[1]//=2
        f=True
    for i in range(N):
        if c==0:
            X^=a[i]%2
        K=N-1-i
        while K>0 and K%2==0:
            c+=1
            K//=2
        K=i+1
        while K>0 and K%2==0:
            c-=1
            K//=2
    if X==1:
        print(1*(f+1))
    else:
        print(0)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    N=int(input())
    a=list(map(int1,input()))
    X=0
    c=0
    for i in range(N):
        if c==0:
            X^=a[i]%2
        K=N-1-i
        while K>0 and K%2==0:
            c+=1
            if K%2==0:
                K//=2
            else:
                break
        K=i+1
        while K>0 and K%2==0:
            c-=1
            if K%2==0:
                K//=2
            else:
                break
    if X==1:
        print(1)
    else:
        if 1 in a:
            print(0)
        else:
            print(2)

if __name__ == '__main__':
    main()